Algorithms Space & Time Complexity Analysis 2

Question 1

What is the amortized time complexity of a single push operation on a dynamic array that doubles in size when full?

Accepted Answer

O(1)

Answer

Although occasional resize operations cost O(n), the cost is spread across all pushes, making the amortized per-push cost O(1).

Question 2

A recursive Fibonacci function fib(n) = fib(n-1) + fib(n-2) without memoization has which time complexity?

Accepted Answer

O(2ⁿ)

Answer

Each call spawns two sub-calls, creating an exponential call tree with approximately 2ⁿ nodes.

Question 3

Which notation describes the best-case lower bound on an algorithm's running time?

Accepted Answer

Big-Omega (Ω)

Answer

Big-Omega (Ω) provides an asymptotic lower bound, meaning the algorithm takes at least that long in the best case.

Question 4

What is the space complexity of a recursive depth-first search (DFS) on a graph with V vertices and E edges?

Accepted Answer

O(V)

Answer

DFS uses the call stack, which in the worst case holds up to V frames (one per vertex on the deepest path), giving O(V) space.

Question 5

Quicksort has an average-case time complexity of O(n log n). What is its worst-case time complexity?

Accepted Answer

O(n²)

Answer

When the pivot is always the smallest or largest element (e.g., sorted input with naïve pivot selection), partitioning is unbalanced and degrades to O(n²).

Algorithms Practice Test

Algorithms Practice Test

Algorithms Space & Time Complexity Analysis 2