Time Complexity Practice — Full

Notes | Codingdidi
@codingdidi

Ques-1

Answer:

def puzzle(n):
for i in range(n): # runs n times
j=1

Time Complexity Practice — Full Notes | Codingdidi 1

 while j < n: # runs log₂(n) times
j=j*2

Outer loop → O(n)

Inner loop → O(log₂ n)

When loops are nested, we multiply:

O(n) × O(log n) = O(n log n)
Key takeaway

Situation What to Do

Nested loops Multiply

Sequential loops Add

Log base Ignore

Ques-2:

look carefully 👀
i is NOT increasing by 1
It grows like this:

1 → 2 → 4 → 8 → 16 → 32 → ...
Let’s count how many times the loop runs.

After k iterations:
i = 2^k

Time Complexity Practice — Full Notes | Codingdidi 2

 Loop stops when:
2^k ≥ n

Taking log on both sides:

k = log₂(n)

✅ Correct Answer
Time Complexity = O(log n)
Reason = The loop variable doubles each iteration, so the number of iterations
grows logarithmically.

Ques-3

Outer loop runs n times

Inner loop runs:

0 times when i = 0

1 time when i = 1

2 times when i = 2

...

(n − 1) times when i = n − 1

Total operations:
0 + 1 + 2 + ... + (n - 1) = n(n - 1)/2

That simplifies to:

Time Complexity Practice — Full Notes | Codingdidi 3

 O(n²)
(Key takeaway)

Even if the inner loop depends on i,

nested growth still leads to O(n²).

Code Pattern Series Type Final TC

i = i * 2 or i = i / 2 Geometric O(log n)

n + n/2 + n/4 + ... Geometric O(n)

1 + 2 + 3 + ... + n Arithmetic O(n²)

Constant work per loop — O(n)

Divide or multiply by a constant ⇒ geometric.

Ques-4

✅ Final—- O(n)
🧠 Why?
Let’s count total work, not loop count.

Values of i:
n + n/2 + n/4 + n/8 + ...

This is a geometric series:

Sum = 2n

So, total operations are linear.

Time Complexity Practice — Full Notes | Codingdidi 4

 Ques-5

✅ Time Complexity
O(n²)

🧠 Reason
Outer loop → n

Inner loop → n/2

Constants ignored → O(n²)

@codingdidi

Ques-6

1️⃣ Outer loop

Runs n times

2️⃣ Inner loop

k starts as i

Time Complexity Practice — Full Notes | Codingdidi 5

 Each iteration: k = k // 2

Number of iterations ≈ log₂(i)

3️⃣ Total Work

log(1) + log(2) + log(3) + ... + log(n)
This sum is bounded by:

n log n

✅ Final Answer
Time Complexity = O(n log n)

@codingdidi

Ques-7

1️⃣ Outer Loop (i = 1; i <= n; i *= 2)

i doubles each iteration → log₂(n) iterations

Time Complexity Practice — Full Notes | Codingdidi 6

 ✅ O(log n)
2️⃣ Middle Loop (j = n; j > 0; j //= 2)
j halves each iteration → log₂(n) iterations

✅ O(log n)
3️⃣ Inner Loop (k = j; k > 1; k //= 2)
k halves each iteration → log₂(j) iterations

j changes each time → total work is log₂(n) + log₂(n/2) + log₂(n/4) + ... ≈

O((log n)²)

4️⃣ Combine Loops

Outer loop: O(log n)

Middle loop: O(log n)

Inner loop: O(log n) (amortized across middle loop)

✅ Total:
O((log n)³)

Ques-8

1️⃣ Outer Loop (i *= 2)

i doubles each time → log₂(n) iterations

Time Complexity Practice — Full Notes | Codingdidi 7

 ✅ O(log n)
2️⃣ Inner Loop (j *= 2 while j < i)
For each outer iteration, j doubles from 1 → i

Number of iterations ≈ log₂(i)

3️⃣ Total Work

Sum of inner loops over outer loop:

log 1 + log 2 + log 4 + log 8 + ... + log n

There are log₂(n) terms, each ≤ log₂(n)

Total ≈ (log n)²

✅ Final Answer
Time Complexity = O((log n)²)
Reason = Outer loop runs log n times, inner loop runs log i times; summing over all
iterations gives (log n)^2.

Ques-9

Time Complexity: O((log n)²)

Time Complexity Practice — Full Notes | Codingdidi 8

 Reason: Outer loop doubles → log n, inner loop doubles to i → log i; sum → (log
n)²

Ques-10

Time Complexity: O((log n)²)

Reason: Outer loop halves → log n, inner loop halves → log j; sum → (log n)²

Ques-11

Time Complexity: O(n log n)

Reason: Outer loop runs n times, inner loop runs log(n/i) times; total sum ≈ n log n

Ques-12

Time Complexity Practice — Full Notes | Codingdidi 9

 Time Complexity: O((log n)³)
Reason: Outer log n, middle log n, inner log n → multiply → (log n)³

Ques- 13

Time Complexity: O(n² log n)

Reason: Outer → n, middle ~ n, inner → log j ≤ log n; multiply → n² log n

Ques-14

Time Complexity Practice — Full Notes | Codingdidi 10

 Time Complexity: O((log n)³)
Reason: All three loops double independently → multiply logs → (log n)³

Ques-15

Time Complexity: O(n log n)

Reason: Outer n, inner log n → multiply → n log n

Ques-16

Time Complexity Practice — Full Notes | Codingdidi 11

 Time Complexity: O((log n)³)
Reason: Three nested halving loops → multiply logs → (log n)³

@codingdidi

Ques- 17

Time Complexity: O(n log n)

Reason: Outer n, inner log i → sum(log i) ≈ n log n

Ques-18

Time Complexity Practice — Full Notes | Codingdidi 12

 Time Complexity: O((log n)³)
Reason: Three nested loops, all doubling/halving independently → multiply → (log
n)³

@codingdidi

Shortcuts
1. Doubling/halving loops → log n

2. Nested independent log loops → multiply logs → (log n)^k

3. Linear × log → n log n

4. Nested loops depending on outer index → sum series carefully

5. Shrinking inner loop often sums to geometric series → O(n)

6. Arithmetic series (0+1+…+n) → O(n²)

Tips while analyzing:

1. Identify if the loop grows/shrinks exponentially → log n

2. If inner loops depend on outer loop → sum series carefully

3. Multiply nested loops, sum loops when bounds shrink

4. Constants don’t matter (Big-O)

5. Look for geometric or arithmetic series

Time Complexity Practice — Full Notes | Codingdidi 13

 Pattern Time Complexity

Single loop O(n)

Multiply/divide loop O(log n)

Nested loops Multiply

Shrinking inner work Often O(n)

Arithmetic series O(n²)

Multiply / divide by a constant ⇒ logarithmic time

Step size doesn’t change Big-O n, n/2, n/10 → all are O(n)

💡 created 💜
by @codingdidi
Helping you enter Big Tech
Instagram | YouTube | Telegram: @codingdidi

Time Complexity Practice — Full Notes | Codingdidi 14