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

O(n)

Answer

O(log n)

Answer

O(n²)

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

O(n)

Answer

O(n log n)

Answer

O(n²)

Question 3

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

Accepted Answer

Big-Omega (Ω)

Answer

Big-O (O)

Answer

Big-Theta (Θ)

Answer

Little-o (o)

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

O(V + E)

Answer

O(E)

Answer

O(1)

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

O(n log n)

Answer

O(n)

Answer

O(log n)

Question 6

If an algorithm runs in O(n log n) time, which of the following input sizes would see the greatest relative slowdown compared to O(n)?

Accepted Answer

n = 1,000,000

Answer

n = 10

Answer

n = 100

Answer

n = 1,000

Question 7

Which data structure allows O(1) average-case insertion, deletion, and lookup?

Accepted Answer

Hash table

Answer

Binary search tree

Answer

Sorted array

Answer

Min-heap