TIME COMPLEXITY

D

Qubits of DPK

April 12, 2026

Core DSA

Loop Patterns – AP & GP Cheat Sheet

1. Simple Linear Loop

java
QUBITS OF DPK
1for (int i = 0; i < n; i++) {
2    // O(1) work
3}
Runs n times.
Iterations = n
TC = O(n)

2. Nested Loop with Equal Range

java
QUBITS OF DPK
1for (int i = 0; i < n; i++) {
2    for (int j = 0; j < n; j++) {
3        // O(1)
4    }
5}
Runs n * n times.
Iterations = n²
TC = O(n²)

3. Nested Loop with Inner Dependent on Outer (AP)

java
QUBITS OF DPK
1for (int i = 0; i < n; i++) {
2    for (int j = 0; j <= i; j++) {
3        // O(1)
4    }
5}
Inner loop runs i+1 times.
Total Iterations = 1 + 2 + 3 + … + n = n(n+1)/2
TC = O(n²)

4. Skip by Constant Step

java
QUBITS OF DPK
1for (int i = 1; i <= n; i += 2) {
2    // O(1)
3}
Runs ~ n/2 times.
Iterations = n/2
TC = O(n)

5. Logarithmic Loop

java
QUBITS OF DPK
1for (int i = 1; i <= n; i *= 2) {
2    // O(1)
3}
Doubles each time → log₂(n) iterations.
Iterations = log n
TC = O(log n)

6. Log Loop Nested in Linear

java
QUBITS OF DPK
1for (int i = 0; i < n; i++) {
2    for (int j = 1; j <= n; j *= 2) {
3        // O(1)
4    }
5}
Outer runs n, inner runs log n.
Iterations = n * log n
TC = O(n log n)

7. GP Series Loop

java
QUBITS OF DPK
1for (int i = 1; i <= n; i++) {
2    for (int j = 1; j <= Math.pow(2, i); j++) {
3        // O(1)
4    }
5}
Inner loop runs 2^i times.
Total Iterations = 2¹ + 2² + … + 2ⁿ = 2^(n+1) - 2
TC = O(2^n)

8. General GP (ratio r)

java
QUBITS OF DPK
1for (int i = 1; i <= n; i++) {
2    for (int j = 1; j <= Math.pow(r, i); j++) {
3        // O(1)
4    }
5}
Inner loop runs r^i times.
Total Iterations = r¹ + r² + … + rⁿ = (r^(n+1) - r) / (r-1)
TC = O(r^n)

9. Decreasing by Division (Logarithmic)

java
QUBITS OF DPK
1for (int i = n; i > 0; i /= 2) {
2    // O(1)
3}
Each step divides → log₂(n) iterations.
Iterations = log n
TC = O(log n)

10. Double Logarithmic

java
QUBITS OF DPK
1for (int i = n; i > 0; i = (int)Math.sqrt(i)) {
2    // O(1)
3}
Shrinks faster than division.
Iterations = log log n
TC = O(log log n)
Quick Interview Tip:
  • If inner loop depends linearly on i → AP → O(n²).
  • If inner loop depends exponentially on i → GP → O(r^n).
  • If loop multiplies/divides index → Logarithmic (log n or log log n).
  • Always sum the iterations like: