Space and Time Complexity

Question 1

What is time complexity?

Answer 1

A measure of the amount of time an algorithm takes as a function of input size.

Question 2

What is space complexity?

Answer 2

A measure of the amount of memory an algorithm uses as a function of input size.

Question 3

What is Big O notation?

Answer 3

A mathematical notation used to describe the upper bound of an algorithm’s runtime or space usage.

Question 4

What does O(1) mean?

Answer 4

Constant time or space — independent of input size.

Question 5

What does O(n) mean?

Answer 5

Linear time or space — grows directly with input size.

Question 6

What does O(log n) mean?

Answer 6

Logarithmic time or space — grows slowly even for large inputs.

Question 7

What does O(n log n) mean?

Answer 7

Linearithmic complexity — typical of efficient sorting algorithms.

Question 8

What does O(n^2) mean?

Answer 8

Quadratic time or space — often results from nested loops.

Question 9

What does O(2^n) mean?

Answer 9

Exponential complexity — grows very quickly with input size.

Question 10

What does O(n!) mean?

Answer 10

Factorial time — extremely slow, used in brute-force permutations.

Question 11

What is worst-case complexity?

Answer 11

The maximum amount of time or space an algorithm can take.

Question 12

What is best-case complexity?

Answer 12

The minimum amount of time or space an algorithm can take.

Question 13

What is average-case complexity?

Answer 13

The expected amount of time or space across typical inputs.

Question 14

What is amortized complexity?

Answer 14

The average time per operation over a sequence of operations.

Question 15

What is auxiliary space?

Answer 15

Extra space or temporary space used by an algorithm.

Question 16

What is in-place algorithm?

Answer 16

An algorithm that uses only a constant amount of extra space.

Question 17

What is the time complexity of binary search?

Answer 17

O(log n)

Question 18

What is the time complexity of linear search?

Answer 18

O(n)

Question 19

What is the space complexity of recursive algorithms?

Answer 19

O(depth of recursion) due to call stack.

Question 20

What is the time complexity of quicksort on average?

Answer 20

O(n log n)

Question 21

What is the worst-case time complexity of quicksort?

Answer 21

O(n^2)

Question 22

What is the time complexity of merge sort?

Answer 22

O(n log n) in all cases.

Question 23

What is the space complexity of merge sort?

Answer 23

O(n) due to auxiliary arrays.

Question 24

What is the time complexity of heap sort?

Answer 24

O(n log n)

Question 25

What is the space complexity of heap sort?

Answer 25

O(1) for in-place version.

Question 26

What is the time complexity of inserting into a heap?

Answer 26

O(log n)

Question 27

What is the time complexity of BFS or DFS using adjacency list?

Answer 27

O(V + E)

Question 28

What is the space complexity of BFS?

Answer 28

O(V) for queue and visited set.

Question 29

What is the time complexity of Dijkstra’s algorithm with a min-heap?

Answer 29

O((V + E) log V)

Question 30

What is the space complexity of storing a graph with adjacency matrix?

Answer 30

O(V^2)

Question 31

What is the time complexity of finding an element in a hash table?

Answer 31

O(1) average, O(n) worst-case.

Question 32

What is the space complexity of a hash table?

Answer 32

O(n)

Question 33

What is the complexity of building a trie with n words of length m?

Answer 33

O(n * m)

Question 34

What is the complexity of searching in a trie?

Answer 34

O(m), where m is the length of the key.

Question 35

What is the time complexity of finding union in disjoint set with path compression?

Answer 35

O(α(n))

Question 36

What is α(n) in time complexity?

Answer 36

The inverse Ackermann function — grows very slowly.

Question 37

What is the difference between Big O, Omega, and Theta?

Answer 37

O is upper bound, Ω is lower bound, Θ is tight bound.

Question 38

What is a tight bound?

Answer 38

An exact asymptotic behavior, expressed using Theta notation.

Question 39

What is the time complexity of matrix multiplication?

Answer 39

O(n^3) for naive method.

Question 40

What is the best-case time complexity of bubble sort?

Answer 40

O(n) when the array is already sorted.

Question 41

What is the worst-case time complexity of bubble sort?

Answer 41

O(n^2)

Question 42

What is the time complexity of inserting into a BST?

Answer 42

O(log n) for balanced trees.

Question 43

What is the worst-case insertion time for unbalanced BST?

Answer 43

O(n)

Question 44

What is the space complexity of an iterative algorithm?

Answer 44

Usually O(1) unless it uses additional data structures.

Question 45

Why is analyzing time complexity important?

Answer 45

To predict how an algorithm scales with input size.

Question 46

Why is analyzing space complexity important?

Answer 46

To ensure efficient memory usage, especially with large inputs.

Question 47

What is the impact of nested loops on time complexity?

Answer 47

Each level of nesting multiplies the complexity, often resulting in O(n^2), O(n^3), etc.