1. Big-O notation

What is Big-O notation?

A way to describe how an algorithm’s runtime or space usage grows as the input size increases, focusing on the growth rate.

What real-world analogy is used to explain Big-O?

Video game loading screens, rating load times based on level size (e.g., O(1) is instant, O(n²) is brutal)!

In the RAM model, what assumptions do we make?

A single processor, unlimited memory, and every basic operation or memory access takes constant time (O(1)).

What does O(1) time complexity mean?

Constant time: the operation takes the same amount of time regardless of input size.

What does O(n) time complexity mean?

Linear time: runtime grows proportionally with the input size.

What does O(n²) time complexity mean?

Quadratic time: runtime grows proportional to the square of the input size, typical of nested loops.

What does O(2ⁿ) time complexity mean?

Exponential time: runtime doubles with each additional element, as in naive recursive subset generation.

Why do we ignore constants and lower-order terms in Big-O?

Because for very large inputs, constants and smaller terms become negligible in the growth rate.

What is amortized time complexity?

The average time per operation over a sequence of operations, smoothing out occasional costly operations (e.g., dynamic array append).

How does linear search leverage sorted data for optimization?

It stops early and returns None as soon as the current element exceeds the target.

Describe the binary search algorithm and its time complexity.

Check the middle element, then recurse or iterate on the half that could contain the target; runs in O(log n) time.

What’s the worst-case vs. average-case vs. amortized analysis?

Worst-case is the maximum time for any input, average-case is expected time over random inputs, amortized is average over a series of operations.

What is time complexity?

A Big-O measure (T(n)) of how an algorithm’s runtime scales with input size.

What is space complexity?

A Big-O measure (S(n)) of how an algorithm’s memory usage scales with input size.

Compare space complexity for reversing an array in place vs. with a copy.

In-place reversal uses O(1) extra space; reversing by copying uses O(n) extra space.