Time Complexity — Essentials

Practice sheet: all 10 questions

Prefer reading first? Every question from this quiz, with the answer and a worked explanation. (Solving them in the quiz above earns XP — up to ≈95.)

1. Q1. What is the worst-case time complexity of binary search on a sorted array of n elements?

   • a. O(1)
   • b. O(log n)
   • c. O(n)
   • d. O(n log n)
   Show answer & explanation

   Answer: B. O(log n)

   Each comparison discards half of the remaining range, so the search space shrinks n → n/2 → n/4 → … → 1 in about log₂n steps. Anything that halves the problem each step is a log — remember binary search needs the array to already be sorted.

2. Q2. A loop runs i = 1 to n, and inside it another loop runs j = 1 to n. What is the overall time complexity?

   • a. O(n)
   • b. O(2n)
   • c. O(n²)
   • d. O(n log n)
   Show answer & explanation

   Answer: C. O(n²)

   Nested loops MULTIPLY: the inner body runs n × n = n² times. Contrast this with two loops written one after the other, which ADD (n + n) and stay O(n) — nesting is what creates the square.

3. Q3. Which of these functions grows the fastest as n becomes very large?

   • a. n²
   • b. n log n
   • c. 2ⁿ
   • d. n³
   Show answer & explanation

   Answer: C. 2ⁿ

   The growth ladder is: log n < n < n log n < n² < n³ < 2ⁿ < n!. Every polynomial (even n¹⁰⁰) is eventually overtaken by an exponential like 2ⁿ — at n = 30, 2ⁿ is already past a billion while n³ is only 27,000.

4. Q4. How many times does this loop iterate: for (i = 1; i < n; i = i * 2)?

   • a. About n times
   • b. About n/2 times
   • c. About log₂ n times
   • d. About √n times
   Show answer & explanation

   Answer: C. About log₂ n times

   i doubles every pass: 1, 2, 4, 8, … and reaches n after about log₂n doublings. Rule of thumb: a loop counter that is multiplied (or divided) by a constant gives O(log n); one that is incremented gives O(n).

5. Q5. What is the time complexity of accessing arr[i] in an ordinary array?

   • a. O(1)
   • b. O(log n)
   • c. O(n)
   • d. O(i)
   Show answer & explanation

   Answer: A. O(1)

   Arrays are contiguous in memory, so the address of arr[i] is computed directly as base + i × elementSize — one arithmetic step regardless of n or i. This O(1) random access is exactly what a linked list gives up (there, reaching index i costs O(i)).

6. Q6. If f(n) = 3n² + 10n + 7, what is the tightest big-O bound for f(n)?

   • a. O(n)
   • b. O(n²)
   • c. O(n³)
   • d. O(log n)
   Show answer & explanation

   Answer: B. O(n²)

   Keep the dominant term and drop constants and lower-order terms: 3n² + 10n + 7 is O(n²). Note the word 'tightest' — O(n³) is technically also an upper bound (big-O only promises 'no worse than'), which is why interviewers phrase it this way.

7. Q7. What is the worst-case time complexity of linear search in an unsorted array?

   • a. O(1)
   • b. O(log n)
   • c. O(n)
   • d. O(n²)
   Show answer & explanation

   Answer: C. O(n)

   With no ordering to exploit, the target can sit at the last position (or be absent), forcing a scan of all n elements. Binary search's O(log n) is not available here — it requires sorted data, which is the trade-off this question tests.

8. Q8. Two separate loops run one AFTER the other, each from 1 to n. The combined time complexity is:

   • a. O(n²)
   • b. O(2n²)
   • c. O(n)
   • d. O(n log n)
   Show answer & explanation

   Answer: C. O(n)

   Sequential loops ADD: n + n = 2n, and constants are dropped, so it stays O(n). Only NESTED loops multiply into O(n²) — 'side by side adds, one inside the other multiplies' settles most loop questions instantly.

9. Q9. Which of these sorting algorithms run in O(n log n) time in the average case? Select all that apply.

   • a. Merge sort
   • b. Quick sort
   • c. Bubble sort
   • d. Heap sort
   Show answer & explanation

   Answer: A. Merge sort · B. Quick sort · D. Heap sort

   Merge sort and heap sort are O(n log n) in every case; quick sort averages O(n log n) though its worst case is O(n²) on bad pivots. Bubble sort is O(n²) on average — comparison sorts simply cannot beat n log n in general.

10. Q10. Exactly how many times does the loop body execute: for (i = 1; i <= 64; i = i * 2)? Enter the number.

    Show answer & explanation

    Answer: 7

    i takes the values 1, 2, 4, 8, 16, 32, 64 — seven iterations, because 64 = 2⁶ and the count is the exponent PLUS one (i starts at 2⁰). Off-by-one on doubling loops is one of the most common exam slips: log₂64 = 6, but the body runs 7 times.