100 Problems on Analysis of Algorithms

Beginner (20 Problems)

1. Time complexity of basic operations (arithmetic, assignment, loops)

2. Calculate the time complexity of nested loops
3. Identify constant, linear, and quadratic time complexities
4. Big-O notation for a simple recursive function
5. Analyze the time complexity of binary search
6. Understanding Big-Omega and Big-Theta notations
7. Analyze time complexity of finding the maximum element in an array
8. Determine the space complexity of an iterative function
9. Differentiate between best-case, worst-case, and average-case complexities
10. Time complexity of insertion in a sorted array
11. Find the complexity of checking for duplicates in a list
12. Derive time complexity of selection sort
13. Space complexity of creating a 2D matrix
14. Big-O for a constant-time operation
15. Basics of amortized analysis (e.g., dynamic array resizing)
16. Analyze time complexity of merging two sorted arrays
17. Worst-case time complexity of bubble sort
18. Space complexity of storing a string
19. Analyze a while loop's runtime
20. Calculate time complexity for finding factorial iteratively

Intermediate (20 Problems)

21. Analyze recursive Fibonacci function's time complexity

22. Complexity analysis of quicksort's partition step
23. Derive the recurrence relation for merge sort
24. Space complexity of depth-first search in a graph
25. Compare complexities of different sorting algorithms
26. Analyze heap sort's time complexity
27. Complexity of finding the GCD using the Euclidean algorithm
28. Explain the time complexity of hash table operations
29. Analyze the complexity of Breadth-First Search (BFS)
30. Solve and analyze Tower of Hanoi's recurrence
31. Space complexity of storing a graph (adjacency list vs matrix)
32. Average-case complexity of quicksort
33. Analyze insertion and deletion in a binary search tree
34. Time complexity of matrix multiplication
35. Explain amortized analysis for push and pop operations in a stack
36. Complexity of finding a cycle in a graph
37. Compare runtime of iterative vs recursive approaches
 38. Analyze a nested recursive function
39. Space complexity of dynamic programming solutions
40. Solve and analyze T(n) = 2T(n/2) + O(n)

Advanced (20 Problems)

41. Analyze the runtime of the Dijkstra algorithm

42. Time complexity of constructing a suffix array
43. Compare Kruskal's vs Prim's algorithm complexities
44. Solve and analyze T(n) = T(n-1) + T(n-2) + O(1)
45. Complexity of the Floyd-Warshall algorithm
46. Analyze the runtime of KMP string matching algorithm
47. Space complexity of memoization in dynamic programming
48. Find complexity bounds for modular exponentiation
49. Analyze runtime of randomized quicksort
50. Explain amortized cost of union-find operations
51. Time complexity of Trie insert and search operations
52. Analyze the runtime of the Rabin-Karp algorithm
53. Explain Master Theorem with examples
54. Complexity analysis of divide and conquer algorithms
55. Solve recurrence: T(n) = T(n/2) + T(n/4) + O(1)
56. Explain lower bounds of comparison-based sorting
57. Analyze the complexity of 2-SUM and 3-SUM problems
58. Compare runtime of naive vs optimized matrix chain multiplication
59. Analyze space complexity of graph coloring problems
60. Complexity of Longest Common Subsequence algorithm

Expert (20 Problems)

61. Solve and analyze T(n) = 3T(n/3) + O(n log n)

62. Analyze the runtime of Bellman-Ford algorithm
63. Complexity of Tarjan's algorithm for finding strongly connected components
64. Space complexity of A* search algorithm
65. Analyze runtime of Strassen's matrix multiplication
66. Compare and analyze complexity of FFT vs naive DFT
67. Solve recurrence: T(n) = T(√n) + log(n)
68. Analyze runtime of suffix tree construction
69. Complexity of dynamic programming solution for TSP
70. Explain amortized analysis of splay trees
71. Complexity analysis of Min-Cut problem
72. Derive and solve the recurrence relation for Karatsuba multiplication
73. Analyze runtime of Hopcroft-Karp algorithm
74. Time complexity of Edmonds-Karp maximum flow algorithm
75. Complexity of finding articulation points in a graph
 76. Space complexity of lazy propagation in segment trees
77. Complexity of Sparse Table for range queries
78. Analyze time complexity of convex hull algorithms
79. Compare runtime of Fibonacci Heap vs Binary Heap operations
80. Analyze complexity of subset-sum problem using dynamic programming

Mastery (20 Problems)

81. Analyze runtime of matrix exponentiation for solving linear recurrences

82. Complexity of the Edmonds blossom algorithm for maximum matching
83. Explain lower bounds for NP-complete problems
84. Solve recurrence: T(n) = 4T(n/2) + n²
85. Analyze runtime of the Z-algorithm for pattern matching
86. Complexity analysis of solving linear programming problems
87. Analyze the runtime of the Schoenhage-Strassen algorithm for fast integer
multiplication
88. Space complexity of solving n-queens problem using backtracking
89. Complexity of solving Maximum Bipartite Matching with augmenting paths
90. Solve recurrence: T(n) = 2T(n/2) + T(n/4) + O(1)
91. Analyze runtime of Dinic's maximum flow algorithm
92. Complexity of solving SAT using the DPLL algorithm
93. Analyze runtime of Viterbi algorithm for Hidden Markov Models
94. Explain complexity of solving the traveling salesman problem with branch and bound
95. Compare runtime of iterative vs recursive FFT
96. Analyze runtime of solving sparse linear systems with Conjugate Gradient Method
97. Explain runtime complexity of primality testing algorithms
98. Analyze complexity of computing PageRank iteratively
99. Complexity analysis of solving integer linear programming
100. Analyze runtime of using Lagrange interpolation in polynomial fitting