Design and Analysis of Algorithms

What is meant by Algorithm Analysis?

Algorithm analysis is an important part of computational complexity theory, which provides theoretical estimation for the required resources of an algorithm to solve a specific computational problem. Analysis of algorithms is the determination of the amount of time and space resources required to execute it.

Why Analysis of Algorithms is important?

• To predict the behavior of an algorithm without implementing it on a specific computer.
• It is much more convenient to have simple measures for the efficiency of an algorithm than to implement the algorithm and test the efficiency every time a certain parameter in the underlying computer system changes.
• It is impossible to predict the exact behavior of an algorithm. There are too many influencing factors.
• The analysis is thus only an approximation; it is not perfect.
• More importantly, by analyzing different algorithms, we can compare them to determine the best one for our purpose.

Types of Algorithm Analysis:

1. Best case
2. Worst case
3. Average case

Basics on Analysis of Algorithms:

1. What is algorithm and why analysis of it is important?
2. Asymptotic Notation and Analysis (Based on input size) in Complexity Analysis of Algorithms
3. Worst, Average and Best Case Analysis of Algorithms
4. Types of Asymptotic Notations in Complexity Analysis of Algorithms
5. How to Analyse Loops for Complexity Analysis of Algorithms
6. How to analyse Complexity of Recurrence Relation
7. Introduction to Amortized Analysis

Asymptotic Notations:

1. Analysis of Algorithms | Big-O analysis
2. Difference between Big Oh, Big Omega and Big Theta
3. Examples of Big-O analysis
4. Difference between big O notations and tilde
5. Analysis of Algorithms | Big – Ω (Big- Omega) Notation
6. Analysis of Algorithms | Big – Θ (Big Theta) Notation

Some Advance topics:

1. Types of Complexity Classes | P, NP, CoNP, NP hard and NP complete
2. Can Run Time Complexity of a comparison-based sorting algorithm be less than N logN?
3. Why does accessing an Array element take O(1) time?
4. What is the time efficiency of the push(), pop(), isEmpty() and peek() operations of Stacks?

Complexity Proofs:

1. Proof that Clique Decision problem is NP-Complete
2. Proof that Independent Set in Graph theory is NP Complete
3. Prove that a problem consisting of Clique and Independent Set is NP Complete
4. Prove that Dense Subgraph is NP Complete by Generalisation
5. Prove that Sparse Graph is NP-Complete

If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above