Analysis of Algorithms

Analysis of Algorithms is a fundamental aspect of computer science that involves evaluating performance of algorithms and programs. Efficiency is measured in terms of time and space.

Basics

• Why is Analysis Important?
• Order of Growth
• Asymptotic Analysis
• Worst, Average and Best Cases

Asymptotic Notations

• Big-O Notation
• Theta - Θ Notation
• Big – Ω (Big- Omega) Notation
• Time Complexity
• Space Complexity
• Big O vs, Big Omega vs Theta
• Examples of Big-O analysis
• Practice Questions on Time Complexity Analysis
• Quiz on Time Complexity Analysis

Analysis Examples

• Analyzing Loops
• Analyzing Recursive Functions
• Amortized Analysis

Some Advance topics

• P, NP, CoNP, NP hard and NP complete
• Proof that Clique Decision problem is NP-Complete
• Proof that Independent Set in Graph theory is NP Complete
• Prove that a problem consisting of Clique and Independent Set is NP Complete
• Prove that Dense Subgraph is NP Complete by Generalisation
• Prove that Sparse Graph is NP-Complete