Algorithm Complexity

Practical Session — Answered Questions

20 Questions 18 Coded 2 Conceptual Full Answers

Notation Name Typical example

O(1) Constant Array index, hash map lookup
O(log n) Logarithmic Binary search
O(n) Linear Single loop, BFS
O(n log n) Log-linear Merge sort, heap sort
O(n^2) Quadratic Bubble sort, nested loops
O(2^n) Exponential Recursive Fibonacci, subsets
O(n!) Factorial Permutations, brute-force TSP
Part 1 — Code Complexity Questions
For each code snippet below, determine the time complexity and space complexity using Big O
notation. Answers and explanations follow each question.

Q Single loop — find maximum O(n)

1
What is the time and space complexity?
def find_max(arr):
max_val = arr[0]
for x in arr: # runs n times
if x > max_val:
max_val = x
return max_val

Answer
O(n)
Time: O(n) | Space: O(1)
The single loop iterates over all n elements once, giving linear time. Only one extra variable (max_val)
is stored regardless of input size, so space is constant.

Q Nested loops — bubble sort O(n^2)

2
What is the time and space complexity?
def bubble_sort(arr):
n = len(arr)
for i in range(n): # outer: n times
for j in range(n - 1): # inner: n-1 times
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr

Answer
O(n^2)
Time: O(n²) | Space: O(1)
Two nested loops each running approximately n times multiply to O(n x n) = O(n²). Sorting is done
in-place, so no extra memory proportional to n is needed.

Q Binary search O(log n)

3
What is the time and space complexity?
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi: # halves search space each step
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
 lo = mid + 1
else:
hi = mid - 1
return -1

Answer
O(log n)
Time: O(log n) | Space: O(1)
Each iteration halves the remaining search space. The loop runs at most log2(n) times. Space is
constant because only index variables are kept.

Q Two-pointer duplicate check O(n^2)

4
What is the time and space complexity?
def has_duplicate(arr):
n = len(arr)
for i in range(n):
for j in range(i + 1, n): # about n*(n-1)/2 pairs
if arr[i] == arr[j]:
return True
return False

Answer
O(n^2)
Time: O(n²) | Space: O(1)
The inner loop starts at i+1 each time, so total comparisons are n(n-1)/2 which is still O(n²). Constant
extra memory is used.

Q Hash-set duplicate check O(n)

5
What is the time and space complexity?
def has_duplicate_fast(arr):
seen = set() # O(n) space
for x in arr: # O(n) time
if x in seen:
return True
[Link](x)
return False

Answer
O(n)
Time: O(n) | Space: O(n)
A single loop and O(1) average-case set operations give linear time. The set can grow up to n entries,
so space is O(n). This is the classic time-space trade-off versus Question 4.

Q Recursive Fibonacci (naive) O(2^n)

6
What is the time and space complexity?
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2) # two recursive calls

Answer
O(2^n)
Time: O(2^n) | Space: O(n)
Each call spawns two more calls, forming a binary tree of depth n, giving roughly 2^n total calls. The
call stack depth is at most n, so space is O(n).

Q Fibonacci with memoisation O(n)

7
What is the time and space complexity?
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]

Answer
O(n)
Time: O(n) | Space: O(n)
Each value from 0 to n is computed exactly once and cached. The recursion tree collapses to a single
path of depth n, giving O(n) time and O(n) space for the memo dictionary and call stack.

Q Merge sort O(n log n)

8
What is the time and space complexity?
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # T(n/2)
right = merge_sort(arr[mid:]) # T(n/2)
return merge(left, right) # O(n)

def merge(L, R):

result, i, j = [], 0, 0
while i < len(L) and j < len(R):
if L[i] <= R[j]: [Link](L[i]); i += 1
else: [Link](R[j]); j += 1
return result + L[i:] + R[j:]
 Answer
O(n log n)
Time: O(n log n) | Space: O(n)
Recurrence T(n) = 2T(n/2) + O(n). By the Master Theorem (case 2) this solves to O(n log n). Auxiliary
arrays used during merging total O(n) space.

Q Linear search in 2-D matrix (row by row) O(n)

9
What is the time and space complexity?
def search_matrix(matrix, target):
for row in matrix: # R rows
for val in row: # C cols
if val == target:
return True
return False

Answer
O(n)
Time: O(n) where n = R x C | Space: O(1)
Every element is visited once. If n denotes the total number of cells (R x C), the complexity is O(n).
Expressed separately it is O(R x C). No extra data structures are used, so space is O(1).

Q
1 Triple nested loop — matrix path count O(n^3)
0
What is the time and space complexity?
def count_triples(arr):
n, count = len(arr), 0
for i in range(n):
for j in range(i, n):
for k in range(j, n):
if arr[i] + arr[j] + arr[k] == 0:
count += 1
return count

Answer
O(n^3)
Time: O(n^3) | Space: O(1)
Three nested loops each running O(n) times yield O(n x n x n) = O(n^3). Constant space is used since
only the counter is stored.

Q
1 Stack-based balanced parentheses O(n)
1
What is the time and space complexity?
def is_balanced(s):
stack = []
pairs = {')':'(', ']':'[', '}':'{'}
for ch in s: # iterates n characters
 if ch in "([{":
[Link](ch)
elif ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
[Link]()
return len(stack) == 0

Answer
O(n)
Time: O(n) | Space: O(n)
One pass over the n characters of s gives O(n) time. In the worst case (all opening brackets) the stack
holds all n characters, so space is O(n).

Q
1 Counting inversions using sorted containers O(n log n)
2
What is the time and space complexity?
import bisect

def count_smaller(nums):
counts, sorted_arr = [], []
for num in reversed(nums): # n iterations
pos = bisect.bisect_left(sorted_arr, num)
[Link](pos)
[Link](sorted_arr, num) # O(n) insert shift
return counts[::-1]

Answer
O(n log n)
Time: O(n^2) | Space: O(n)
bisect_left is O(log n) but insort must physically shift elements in the list, making each insert O(n).
Across n numbers the total is O(n^2). A true O(n log n) solution requires a Fenwick tree or merge sort.

Q
1 BFS on a graph O(n)
3
What is the time and space complexity?
from collections import deque

def bfs(graph, start):

visited = set([start])
queue = deque([start])
while queue:
node = [Link]()
for neighbour in graph[node]:
if neighbour not in visited:
[Link](neighbour)
[Link](neighbour)
 Answer
O(n)
Time: O(V + E) | Space: O(V)
Each vertex is enqueued once (O(V)) and each edge is examined once (O(E)), giving O(V + E) time.
The visited set and queue together hold at most V vertices, so space is O(V).

Q
1 Recursive sum of digits O(n)
4
What is the time and space complexity?
def digit_sum(n):
if n < 10:
return n
return (n % 10) + digit_sum(n // 10)

Answer
O(n)
Time: O(d) = O(log n) | Space: O(d) = O(log n)
The number of recursive calls equals the number of digits d, which is floor(log10(n)) + 1 — so O(log n).
Each call uses one stack frame, giving the same O(log n) space.

Q
1 Insertion sort O(n^2)
5
What is the time and space complexity?
def insertion_sort(arr):
for i in range(1, len(arr)): # n-1 outer iterations
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key: # up to i shifts
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr

Answer
O(n^2)
Time: O(n^2) worst case | Space: O(1)
In the worst case (reverse-sorted input) the inner while loop performs i shifts for each i, totalling
1+2+...+(n-1) = n(n-1)/2 = O(n^2). Best case (already sorted) is O(n). In-place sorting means O(1)
space.

Q
1 Power set generation O(n)
6
What is the time and space complexity?
def power_set(s):
result = [[]]
for elem in s:
result += [subset + [elem] for subset in result]
 return result

Answer
O(n)
Time: O(n * 2^n) | Space: O(n * 2^n)
A set of n elements has 2^n subsets. The list comprehension in iteration i copies all current subsets
(2^(i-1) of them). Summing gives O(2^n) total copy operations, each copying a subset of average length
n/2, yielding O(n * 2^n) time and the same space to store all subsets.

Q
1 Fast exponentiation (divide and conquer) O(log n)
7
What is the time and space complexity?
def fast_pow(base, exp):
if exp == 0:
return 1
if exp % 2 == 0:
half = fast_pow(base, exp // 2) # halves exp
return half * half
return base * fast_pow(base, exp - 1)

Answer
O(log n)
Time: O(log n) | Space: O(log n)
The exponent is halved on even steps, so the recursion depth is O(log n). Each recursive call uses one
stack frame, giving O(log n) space.

Q
1 Kadane's algorithm — maximum subarray O(n)
8
What is the time and space complexity?
def max_subarray(arr):
max_sum = cur_sum = arr[0]
for x in arr[1:]: # single pass: O(n)
cur_sum = max(x, cur_sum + x)
max_sum = max(max_sum, cur_sum)
return max_sum

Answer
O(n)
Time: O(n) | Space: O(1)
One pass through the array, updating two variables at each step. Constant extra space regardless of
input size.
Part 2 — Conceptual Questions
These questions test your deeper understanding of complexity theory and algorithm design trade-offs.

Q
1 Big O vs Big Theta vs Big Omega
9
Explain the difference between Big O (O), Big Theta (Θ), and Big Omega (Ω) notation. When is it most
useful to use each one? Give an example algorithm for each.

Answer
Big O is an upper bound (worst case), Big Omega is a lower bound (best case), and Big Theta is a
tight bound (both upper and lower).
Big O (O): "the algorithm runs in AT MOST this fast." Used in practice because we care most about the
worst case. Example: linear search is O(n) — in the worst case we scan all n elements.

Big Omega (Ω): "the algorithm takes AT LEAST this long." Useful for proving lower-bound limits.
Example: any comparison-based sort is Ω(n log n) — no such algorithm can do better in the worst case.

Big Theta (Θ): the algorithm grows exactly at this rate (constant factors aside). Merge sort is Θ(n log n)
because it is both O(n log n) and Ω(n log n) regardless of input. Use Θ when best and worst cases
share the same growth rate.

Q
2 Space-time trade-off in practice
0
A function checks whether any value appears twice in an integer array. Describe two different
algorithmic approaches, state the time and space complexity of each, and explain in what real-world
situations you would prefer one over the other.

Answer
Approach 1: Nested loops — O(n^2) time, O(1) space. Approach 2: Hash set — O(n) time, O(n)
space.
Approach 1 (brute force nested loops): compare every pair of elements. No extra memory needed.
Preferred when n is small or memory is severely constrained (e.g. embedded systems with kilobytes of
RAM).

Approach 2 (hash set): insert each element; return True if already present. Linear time at the cost of
extra O(n) memory. Preferred for large datasets where speed matters and memory is available (e.g.
web servers, data pipelines).

The general principle: you can almost always trade memory for speed. Dynamic programming,
memoisation, and caching are all manifestations of this same trade-off.