Time & Space Complexity

Q: Is the Time & Space Complexity quiz free?

Yes. The Time & Space Complexity quiz is completely free with no signup. Answer the questions, get instant scoring, and earn XP as you go.

Q: What level is the Time & Space Complexity quiz?

This is a Hard-level quiz. Each question includes the correct answer so you learn as you test yourself, whatever your starting point.

Q: How can I prepare for this quiz?

Review the linked courses and notes for the topic first, then take the quiz to check your understanding. You can retake it anytime to track improvement.

Question 1

Which operation is an example of O(1) — constant time complexity?

Accepted Answer

Array access by index is O(1): the memory address is computed as base_address + (index × element_size) in a single step, regardless of array size. Other O(1) examples: hash table lookup (average), push/pop on a stack, getting the size of a linked list (if tracked).

Question 2

Which of the following is a classic example of an O(log n) algorithm?

Accepted Answer

Binary search halves the search space with each step, requiring at most log₂(n) comparisons. Other O(log n) examples: tree operations in a balanced BST, finding a value in a heap, and Euclid's GCD algorithm. The key signature: the problem size halves (or reduces by a constant fraction) each step.

Question 3

An algorithm is O(n). A second algorithm is O(n²). For what input sizes is the O(n) algorithm meaningfully faster?

Accepted Answer

Big O describes growth rate: O(n²) grows quadratically while O(n) grows linearly. For small n (e.g., n = 5), an O(n²) algorithm might run faster due to lower constant factors. But as n grows (thousands, millions), the O(n) algorithm becomes dramatically faster. At n = 1,000,000: O(n) does ~1M ops vs O(n²) doing ~10¹² ops.

Question 4

What is the space complexity of a recursive function that calls itself n times before reaching the base case?

Accepted Answer

Each recursive call adds a new stack frame to the call stack. If the function recurses n times before hitting the base case and returning, the call stack holds n frames simultaneously, using O(n) space. Tail-call optimization (in some languages) can reduce this to O(1), but it is not universally supported.

Question 5

What is the difference between best-case, worst-case, and average-case complexity?

Accepted Answer

Best case: most favorable input (e.g., target is the first element in linear search — O(1)). Worst case: least favorable input (target not present — O(n)). Average case: expected performance across all inputs of size n, often assuming a probability distribution. Big O typically refers to worst case in interviews unless specified otherwise.

Question 6

What is amortized analysis, and why is it useful?

Accepted Answer

Amortized analysis spreads the cost of infrequent expensive operations over many cheap ones. Classic example: dynamic array append is O(n) when doubling (copying all elements), but O(1) amortized because doubling happens rarely. The total cost for n appends is O(n), so each append costs O(1) on average.

Question 7

Which sorting algorithm has O(n log n) time complexity in all cases (best, average, and worst)?

Accepted Answer

Merge Sort guarantees O(n log n) in all cases because it always divides the array in half (O(log n) levels) and merges each level in O(n). Quick Sort is O(n log n) average but O(n²) worst case. Heap Sort is also O(n log n) in all cases, but Merge Sort is the most commonly cited example.

Question 8

For large values of n, which complexity is faster: O(log n) or O(√n)?

Accepted Answer

O(log n) grows much slower than O(√n). For n = 1,000,000: log₂(1,000,000) ≈ 20, while √1,000,000 = 1,000. Logarithmic algorithms (binary search, balanced tree operations) are faster than square-root algorithms for large inputs. The hierarchy: O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²).

Question 9

The Master Theorem provides a solution for recurrences of the form T(n) = aT(n/b) + f(n). What does it help you determine?

Accepted Answer

The Master Theorem solves recurrences of the form T(n) = aT(n/b) + f(n), where a ≥ 1 subproblems each of size n/b are solved recursively with f(n) work to combine. It has three cases based on how f(n) compares to n^(log_b a). For Merge Sort: T(n) = 2T(n/2) + O(n) → O(n log n).

Question 10

What is the difference between Big-Omega (Ω) and Big-Theta (Θ) notation?

Accepted Answer

Big-O is an upper bound (worst case or better). Big-Omega (Ω) is a lower bound (at least this fast). Big-Theta (Θ) is a tight bound — the algorithm's growth rate is exactly f(n) up to constant factors. Example: Merge Sort is Θ(n log n) because it is always between c₁(n log n) and c₂(n log n). Big-O is most commonly used in practice.

Time & Space Complexity

Frequently Asked Questions

Is the Time & Space Complexity quiz free?

What level is the Time & Space Complexity quiz?

How can I prepare for this quiz?

Learn the Topic

Algorithms Course

Data Structures Course

Go deeper on this topic

Time & Space Complexity

Frequently Asked Questions

Is the Time & Space Complexity quiz free?

What level is the Time & Space Complexity quiz?

How can I prepare for this quiz?

Learn the Topic

Algorithms Course

Data Structures Course

Go deeper on this topic