2.3 Algorithms

Question 1

Big O notation purpose

Answer 1

Describes upper bound of time/space complexity relative to input size.

Question 2

O(1) complexity

Answer 2

Constant time (e.g., array index lookup).

Question 3

O(log n) complexity

Answer 3

Logarithmic (e.g., binary search).

Question 4

O(n) complexity

Answer 4

Linear (e.g., linear search).

Question 5

O(n log n) complexity

Answer 5

Log-linear (e.g., merge sort, quick sort average).

Question 6

O(n²) complexity

Answer 6

Quadratic (e.g., bubble sort, nested loops).

Question 7

O(2ⁿ) complexity

Answer 7

Exponential (e.g., recursive Fibonacci).

Question 8

Space complexity

Answer 8

Measures amount of memory an algorithm uses relative to input size.

Question 9

Depth-first search (DFS)

Answer 9

Explores as far as possible down a branch before backtracking. Uses stack (or recursion).

Question 10

Breadth-first search (BFS)

Answer 10

Explores all neighbours at current depth before moving deeper. Uses queue.

Question 11

Dijkstra’s algorithm use

Answer 11

Finds shortest path from source to all nodes in weighted graph (non-negative weights).

Question 12

A* algorithm difference to Dijkstra

Answer 12

Uses heuristics to estimate distance to target; more efficient.

Question 13

A* requirement

Answer 13

Requires a heuristic function (e.g., Manhattan distance, Euclidean distance).

Question 14

Bubble sort complexity

Answer 14

O(n²) worst case; simple but inefficient.

Question 15

Insertion sort complexity

Answer 15

O(n²) worst case; efficient for small or nearly sorted datasets.

Question 16

Merge sort complexity

Answer 16

O(n log n); stable; divide and conquer; requires additional memory.

Question 17

Quick sort complexity

Answer 17

O(n log n) average; O(n²) worst; in-place variant exists.

Question 18

Binary search requirement

Answer 18

Data must be sorted; O(log n).

Question 19

Linear search complexity

Answer 19

O(n); works on unsorted data.