Algorithm Analysis: Asymptotic Bounds, Cost Models, and Practical Performance

All flashcards

What is algorithm analysis?

The study of the computational resources an algorithm requires, often expressed as a function of input size.

What is time complexity?

A description of how an algorithm's execution-step count grows as its input size grows.

What is space complexity?

A description of how an algorithm's storage or memory requirements grow with input size.

How do best, worst, and average cases differ?

They describe performance on the most favorable input, least favorable input, and expected inputs under an assumed distribution, respectively.

Uniform versus logarithmic cost model?

The uniform model assigns constant cost to each operation; the logarithmic model makes cost proportional to the number of bits involved.

Quiz questions

1. What does Big Theta notation express about a function's asymptotic growth?Answer: A tight bound, with upper and lower bounds proportional to the same function.
2. Under a unit-time lookup assumption, how does binary search on a sorted list scale with its size?Answer: Its number of steps grows logarithmically with the list size.
3. Why can benchmarks alone not establish an algorithm's general efficiency?Answer: They measure selected inputs, implementations, machines, and environments rather than every possible case.
4. What can an exponent estimated from timing measurements in a power-law model establish?Answer: Empirical evidence about observed growth, but not a proof of complexity.
5. What must be shown to prove that a function $f(n)$ is $O(n^2)$?Answer: There are constants $c>0$ and $n_0$ such that $f(n)\leq cn^2$ for all $n\geq n_0$.