Algorithm Analysis and Complexity

Question 1

What is time complexity

Answer 1

a measure of how an algorithms runtime grows with input size.

Question 2

What is Big-O notation?

Answer 2

A mathematical notation describing an algorithm’s worst-case growth rate.

Question 3

What are common time complexities from best to worst?

Answer 3

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).

Question 4

What does Big-O notation describe?

Answer 4

The upper bound of an algorithm’s growth rate (worst-case performance).

Question 5

What is Omega (Ω) notation?

Answer 5

The lower bound of an algorithm’s growth rate (best-case performance).

Question 6

What is Theta (Θ) notation?

Answer 6

The tight bound—both the upper and lower bounds of an algorithm’s growth rate.

Question 7

What is amortized complexity?

Answer 7

The average time per operation over a sequence of operations (e.g., resizing an array-based dynamic list).

Question 8

Give an example of an algorithm with O(1) time complexity.

Answer 8

Hash table lookup (assuming no collisions).

Question 9

What is an invariant in algorithms?

Answer 9

A property that remains true at each step of execution (used in loop invariants).

Question 10

How do you prove an algorithm is correct?

Answer 10

Using induction or loop invariants.