How to calculate the time complexity of recursive functions?
The time complexity of a recursive function can be written as a mathematical recurrence relation. To calculate time complexity, we must know how to solve recurrences. We will soon be discussing recurrence-solving techniques as a separate post.
Algorithms Cheat Sheet:
Algorithm | Best Case | Average Case | Worst Case |
Selection Sort | O(n^2) | O(n^2) | O(n^2) |
Bubble Sort | O(n) | O(n^2) | O(n^2) |
Insertion Sort | O(n) | O(n^2) | O(n^2) |
Tree Sort | O(nlogn) | O(nlogn) | O(n^2) |
Radix Sort | O(dn) | O(dn) | O(dn) |
Merge Sort | O(nlogn) | O(nlogn) | O(nlogn) |
Heap Sort | O(nlogn) | O(nlogn) | O(nlogn) |
Quick Sort | O(nlogn) | O(nlogn) | O(n^2) |
Bucket Sort | O(n+k) | O(n+k) | O(n^2) |
Counting Sort | O(n+k) | O(n+k) | O(n+k) |
Quiz on Analysis of Algorithms
For more details, please refer: Design and Analysis of Algorithms.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
How to Analyse Loops for Complexity Analysis of Algorithms
We have discussed Asymptotic Analysis, Worst, Average and Best Cases and Asymptotic Notations in previous posts. In this post, an analysis of iterative programs with simple examples is discussed.
The analysis of loops for the complexity analysis of algorithms involves finding the number of operations performed by a loop as a function of the input size. This is usually done by determining the number of iterations of the loop and the number of operations performed in each iteration.
Here are the general steps to analyze loops for complexity analysis:
Determine the number of iterations of the loop. This is usually done by analyzing the loop control variables and the loop termination condition.
Determine the number of operations performed in each iteration of the loop. This can include both arithmetic operations and data access operations, such as array accesses or memory accesses.
Express the total number of operations performed by the loop as a function of the input size. This may involve using mathematical expressions or finding a closed-form expression for the number of operations performed by the loop.
Determine the order of growth of the expression for the number of operations performed by the loop. This can be done by using techniques such as big O notation or by finding the dominant term and ignoring lower-order terms.
Contact Us