Questions: Time and Space Complexity

Question 1

An algorithm contains a loop that runs n times, and inside that loop another loop that runs log n times. What is its time complexity?

• A. O(n)
• B. O(log n)
• C. O(n log n)
• D. O(n²)

Answer: (C)

The outer loop runs n iterations and the inner loop runs log n iterations per outer iteration, giving n × log n total operations. This is O(n log n), the complexity of efficient sorting algorithms like merge sort. It grows much more slowly than O(n²) — for n=1,000,000, O(n log n) is about 20 million operations while O(n²) is a trillion.

Question 2

Big-O notation typically describes the worst-case running time of an algorithm.

• T. True
• F. False

Answer: False

Big-O describes an upper bound on growth rate, but it can be applied to best-case, average-case, or worst-case scenarios. For example, quicksort has O(n log n) average-case but O(n²) worst-case — both expressed in Big-O. The confusion arises because worst-case analysis is the most common and practically useful, so Big-O is often used for worst-case by convention, but the notation itself does not specify which case.

Question 3

Why might you choose an algorithm with higher time complexity if it has lower space complexity?

Model answer: When memory is the bottleneck — such as on embedded systems, when working with data too large to fit in RAM, or when cache efficiency matters more than raw operation count — a more memory-frugal algorithm can outperform a theoretically faster one in practice.

Complexity analysis measures growth rate in an idealized model, but real hardware has memory hierarchies (L1/L2/L3 cache, RAM, disk). An algorithm that needs O(n) auxiliary space may thrash the cache or require paging to disk for large inputs, making its actual runtime worse than an in-place O(n²) algorithm. This time-space trade-off is fundamental to practical algorithm selection.