Algorithms Space & Time Complexity Analysis

Question 1

What is the time complexity of binary search on a sorted array of n elements?

Accepted Answer

O(log n)

Answer

Binary search halves the search space each iteration, resulting in O(log n) comparisons.

Question 2

Which Big-O notation describes the worst-case time complexity of bubble sort?

Accepted Answer

O(n²)

Answer

Bubble sort requires nested loops, each running up to n iterations, yielding O(n²) in the worst case.

Question 3

An algorithm with O(1) space complexity means:

Accepted Answer

It uses a constant amount of extra memory regardless of input size

Answer

O(1) space (constant space) means the algorithm uses a fixed amount of additional memory that does not grow with input size.

Question 4

What is the time complexity of accessing an element by index in a dynamic array (e.g., Python list)?

Accepted Answer

O(1)

Answer

Dynamic arrays store elements contiguously in memory, so index-based access is a direct memory lookup in O(1).

Question 5

The recurrence T(n) = 2T(n/2) + O(n) describes which well-known algorithm's complexity?

Accepted Answer

Merge sort

Answer

Merge sort divides the array into two halves (2T(n/2)) and then merges them in O(n), matching this recurrence whose solution is O(n log n).

Algorithms Practice Test