Problems
For loop
Simple for loop
int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + 5;
}
for (j = 0; j < M; j++) {
b = b + 5;
}
//Time O(N+M), Space O(1)Nested for loop
int a = 0, b = 0;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
a = a + j;
}
}
for (k = 0; k < N; k++) {
b = b + k;
}
//Time O(N^2), Space O(1)Check if Prime number
Calculate Square root
Array Copy
While loop
Simple while loop
Sum of Digits
Recursion
Divide and Conquer Method
The function searches for the occurrences of the element k in a sorted vector V using a recursive approach.
Base Case: If the
startindex exceeds theendindex, it returns 0 (no match found).Divide and Conquer:
If V[mid]<k, search the right half of the array (mid+1 to end).
If V[mid]>k, search the left half of the array (start to mid−1).
When V[mid]==k:
Count this occurrence of k (+1) and recursively search both the left and right halves to count all other occurrences.
Minimum Path
The function findMinPath computes the minimum path sum from the top-left corner (0,0) to the bottom-right corner (R−1,C−1) of a matrix V by recursively exploring the possible paths. At every cell, the function can move:
Down (r+1,c)
Right (r,c+1)
The function returns the minimum sum of the path.
Minimum Path with Dynamic Programming (DP)
The above implementation recomputes the results for overlapping subproblems, which makes it inefficient. To improve the time complexity, we can use Dynamic Programming (DP) with memoization or tabulation.
Exponential Growth
Sum of all values of Balanced Binary Search Tree
The function performs a recursive in-order traversal of a binary tree:
It visits each node once (
O(N)time complexity).Uses recursive calls to traverse the left and right subtrees.
Factorial of a number
Permutations of a string
Fibonacci Number
All Fibonacci numbers from 0 to n with recursion
All Fibonacci from 0 to n numbers with memoization
Powers of 2 from 1
Compute a^b with recursion
Square root of a number by guessing
Miscellaneous Problems
GCD with Euclidean algorithm
This is Euclidean algorithm which repeatedly replaces the pair (n, m) with (m , n mod m) until m=0. The result is the greatest common divisor (GCD) of n and m .
Different For loops
A) for (i = 0; i < n; i++)
Loop Analysis:
The loop starts at i=0 and increments by 1 (i++) until i<n.
The number of iterations is directly proportional to nn.
Time Complexity: O(n)
B) for (i = 0; i < n; i += 2)
Loop Analysis:
The loop starts at i=0 and increments by 2 (i+=2) until i<n.
Since the increment step is 2, the number of iterations will be approximately half the size of n. Number of iterations=⌈n/2⌉
Time Complexity: O(n)
Although the number of iterations is halved compared to Case A, the time complexity remains O(n) because constants are ignored in Big-O notation.
C) for (i = 1; i < n; i = 2)
Loop Analysis:
The loop starts at i=1 and multiplies by 2 (i∗=2) until i<n.
The value of i follows the sequence: 1,2,4,8,… The loop runs while i<n.
The number of iterations corresponds to the number of times ii can be doubled before it exceeds nn:Number of iterations=⌊log2(n)⌋
Time Complexity: O(logn)
This is more efficient than both A and B because the growth rate is logarithmic, much smaller than linear.
D) for (i = n; i > -1; i /= 2)
Loop Analysis:
The loop starts at i=n and divides i by 2 (i/=2) until i>−1.
The value of i follows the sequence: n,n/2,n/4,…n. The loop runs while i>−1. Loop will not end since i will stuck at 0.
Check the boundness
Check the growth rate
For and While loop
Which of the following are equivalent to O(N)?
O(N + P), where P < X 0(2N) O(N + log N) O(N + M)
All but the last one are equivalent to O(N) because there is no established relationship between N and M, so we have to keep both variables in there.
String Array Sorting
Suppose we had an algorithm that took in an array of strings, sorted each string, and then sorted the full array. What would the runtime be?
Let s be the length of the longest string. Let a be the length of the array.
Sorting each string is 0( s log s). We have to do this for every string (and there are a strings), so that's 0( a* s log s). Now we have to sort all the strings. There are a strings, so we'll may be inclined to say that this takes O ( a log a) time. We should also take into account that we need to compare the strings. Each string comparison takes O(s) time. There are O(a log a) comparisons, therefore this will take 0( a*s log a) time.
Then runtime will be 0( a* s ( log a + log s)).
Intersection (the number of elements in common) of two arrays
Last updated
