Q: Rank these from fastest to slowest growth: O(n), O(1), O(n log n), O(n²), O(2ⁿ)

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). Exponential is worst; constant is best.

Q: What is the time complexity of linear search, and why?

O(n). In the worst case, you must check every element. Best case O(1), average O(n), but Big-O reports worst-case.

Q: Why is binary search O(log n) instead of O(1)?

Each comparison eliminates half the remaining elements. You need log₂(n) comparisons maximum. Requires a sorted input and random-access data structure.

Q: What is the time-space trade-off? Give an example.

Improving time complexity often increases space complexity. Example: hash table lookups are O(1) time but use O(n) space; binary search is O(log n) time and O(1) space.

Q: Why can an O(n²) algorithm outperform an O(n log n) algorithm in practice?

Big-O ignores constants. O(n²) with tiny constant (c₁·n²) may run faster than O(n log n) with large constant (c₂·n log n) for small n. Also: cache locality and hardware effects matter.

Q: What does amortized analysis mean, and when is it used?

Average cost per operation over a sequence of operations, even if individual operations vary. Used for dynamic arrays: O(1) amortized insertion despite occasional O(n) resizing.

Q: Explain the difference between O(n) and Θ(n).

O(n) is an upper bound (worst-case or better). Θ(n) is a tight bound (both upper and lower). Θ(n) means the algorithm is always Θ(n)—better when you know both bounds.

Q: What is the practical significance of the gap between O(n) and O(n²) at n=1,000,000?

O(n) = ~1 million operations; O(n²) = ~1 trillion operations. At modern CPU speeds (~10⁹ ops/sec), that's milliseconds vs. hours. Scale matters enormously in practice.

Question 1

What does Big-O notation describe?

Accepted Answer

The upper bound on how an algorithm's runtime or space grows as input size n approaches infinity. It captures worst-case behavior.

Question 2

Why use Big-O instead of exact operation counts?

Accepted Answer

Exact counts depend on hardware and implementation details. Big-O abstracts away constants and low-order terms, revealing how algorithms scale—what matters for large inputs.

Question 3

Rank these from fastest to slowest growth: O(n), O(1), O(n log n), O(n²), O(2ⁿ)

Accepted Answer

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). Exponential is worst; constant is best.

Question 4

What is the time complexity of linear search, and why?

Accepted Answer

O(n). In the worst case, you must check every element. Best case O(1), average O(n), but Big-O reports worst-case.

Question 5

Why is binary search O(log n) instead of O(1)?

Accepted Answer

Each comparison eliminates half the remaining elements. You need log₂(n) comparisons maximum. Requires a sorted input and random-access data structure.

Question 6

What is the time-space trade-off? Give an example.

Accepted Answer

Improving time complexity often increases space complexity. Example: hash table lookups are O(1) time but use O(n) space; binary search is O(log n) time and O(1) space.

Question 7

Why can an O(n²) algorithm outperform an O(n log n) algorithm in practice?

Accepted Answer

Big-O ignores constants. O(n²) with tiny constant (c₁·n²) may run faster than O(n log n) with large constant (c₂·n log n) for small n. Also: cache locality and hardware effects matter.

Question 8

What does amortized analysis mean, and when is it used?

Accepted Answer

Average cost per operation over a sequence of operations, even if individual operations vary. Used for dynamic arrays: O(1) amortized insertion despite occasional O(n) resizing.

Question 9

Explain the difference between O(n) and Θ(n).

Accepted Answer

O(n) is an upper bound (worst-case or better). Θ(n) is a tight bound (both upper and lower). Θ(n) means the algorithm is always Θ(n)—better when you know both bounds.

Question 10

What is the practical significance of the gap between O(n) and O(n²) at n=1,000,000?

Accepted Answer

O(n) = ~1 million operations; O(n²) = ~1 trillion operations. At modern CPU speeds (~10⁹ ops/sec), that's milliseconds vs. hours. Scale matters enormously in practice.

Big-O Notation flashcards, generated for you.

Example Big-O Notation flashcards

Make your own Big-O Notation study set

Flashcards for related topics

Big-O Notation flashcards, generated for you.

Example Big-O Notation flashcards

Make your own Big-O Notation study set

Flashcards for related topics