Complexity Analysis of Selected Algorithms
Recursion
1. Fibonacci Sequence
- Time Complexity: O(2^n) (naive recursion), O(n) (with memoization)
- Auxiliary Space: O(n) (recursive call stack or memoization)
2. Climbing Stairs
- Time Complexity: O(2^n) (naive recursion), O(n) (with memoization)
- Auxiliary Space: O(n) (recursive call stack or memoization)
3. Reverse String
- Time Complexity: O(n)
- Auxiliary Space: O(n) (recursive call stack)
4. Happy Number
- Time Complexity: O(log n) (number of digits in n)
- Auxiliary Space: O(log n) (recursive call stack)
5. Greatest Common Divisor (GCD)
- Time Complexity: O(log(min(a, b)))
- Auxiliary Space: O(log(min(a, b))) (recursive call stack)
6. Strobogrammatic Number II
- Time Complexity: O(5^(n/2)) (due to symmetric recursive structure)
- Auxiliary Space: O(n) (recursive call stack)
Divide and Conquer
1. Quick Sort
- Best Time Complexity: O(n log n)
- Average Time Complexity: O(n log n)
- Worst Time Complexity: O(n^2)
- Auxiliary Space: O(log n) (recursive call stack)
Complexity Analysis of Selected Algorithms
2. Merge Sort
- Best, Average, Worst Time Complexity: O(n log n)
- Auxiliary Space: O(n) (temporary arrays)
3. Majority Element
- Time Complexity: O(n log n) (using divide and conquer)
- Auxiliary Space: O(log n) (recursive call stack)
4. Calculate pow(x, n)
- Time Complexity: O(log n)
- Auxiliary Space: O(log n) (recursive call stack)
Binary Search
1. Median of Two Sorted Arrays
- Time Complexity: O(log(min(m, n))) (binary search on smaller array)
- Auxiliary Space: O(1)
2. Find the Fixed Point in a Given Array
- Time Complexity: O(log n)
- Auxiliary Space: O(1)
3. Find Smallest Common Element in All Rows
- Time Complexity: O(m * log n) (binary search for each row)
- Auxiliary Space: O(1)
4. Longest Common Prefix
- Time Complexity: O(n * log m) (binary search on prefix length)
- Auxiliary Space: O(1)
5. Koko Eating Bananas
Complexity Analysis of Selected Algorithms
- Time Complexity: O(n * log h), where h is the maximum pile size
- Auxiliary Space: O(1)
Greedy Method
1. Minimum Product Subset of an Array
- Time Complexity: O(n)
- Auxiliary Space: O(1)
2. Best Time to Buy and Sell Stock
- Time Complexity: O(n)
- Auxiliary Space: O(1)
3. Knapsack Problem (Fractional)
- Time Complexity: O(n log n) (sorting items by value/weight ratio)
- Auxiliary Space: O(1) if done in-place
4. Minimum Cost Spanning Trees
- Kruskal's Algorithm:
- Time Complexity: O(E log E) + O(E * 4 * alpha), where 'E' times for sorting and union-find.
- Auxiliary Space: O(N) (parent array + rank array)
- Prim's Algorithm:
- Using adjacency matrix and linear search: O(|V|^2)
- Using adjacency list and binary heap: O(|E| log |V|)
- Using adjacency list and Fibonacci heap: O(|E| + |V| log |V|)
5. Single Source Shortest Path Problem (Dijkstra's Algorithm)
- Time Complexity:
- Using a simple implementation with an array: O(V^2)
- Using a priority queue (min-heap): O((V + E) log V)
- Auxiliary Space: O(V) (distance array and priority queue)
