Study 09. Evaluating Algorithm Efficiency with 12 free online flashcards. Review key terms, definitions, and concepts with this interactive flashcard deck.
Why analyze algorithms instead of timing one program run?
Algorithm analysis estimates how resource requirements change as input size grows, making comparisons less dependent on hardware, language, compiler, and other system conditions.
What are the two principal resources in algorithm analysis?
Time complexity measures computational work; space complexity measures memory required while the algorithm runs.
What does n represent in algorithm analysis?
Input size is problem-dependent: for an array it is usually the number of elements, while for a binary number it is the number of bits.
What is a cost model?
A cost model specifies which operations count as basic operations, such as assignments, comparisons, arithmetic operations, array accesses, and Boolean tests.
How are sequential algorithm sections analyzed?
Costs of consecutive sections are added. For example, O(n) + O(n) = O(2n), which simplifies to O(n) because constant factors are ignored.
What is the complexity of two nested loops, each running n times?
The inner statement executes n × n = n² times, so the nested loops have O(n²) running time.
Why does repeatedly halving a problem take O(log n) time?
Repeatedly halving the remaining work takes O(log n) time because after k iterations the remaining amount is approximately n/2^k.
What are best-case, worst-case, and average-case analysis?
Best case is the least work for inputs of size n; worst case is the greatest; average case is the expected work under an assumed input distribution.
What does T(n) ∈ O(f(n)) mean?
Big-O is an asymptotic upper bound: T(n) ≤ c f(n) for suitable positive constants c and n₀ and all n ≥ n₀.
How is the dominant term used to classify growth?
In 4n² + 7n + 12, the n² term eventually dominates, so the function has quadratic growth: Θ(n²).
What does Big-Ω notation describe?
Big-Ω describes an asymptotic lower bound: the algorithm requires at least a proportional amount of work represented by f(n) for sufficiently large n.
What does T(n) ∈ Θ(f(n)) mean?
Big-Θ is a tight asymptotic bound: T(n) is both O(f(n)) and Ω(f(n)).