Tutorial 2: The Efficiency of Algorithms and Computing Procedures
Unit 2 ยท Section 2
Objectives
Describe time and space growth.
Use Big-O as a comparison tool.
Recognize trade-offs between speed and memory.
Efficiency asks how resource use grows with input size. Big-O describes an upper growth category while ignoring constants. A single pass is often $O(n)$; nested independent scans are often $O(n^2)$; binary search on sorted data is $O(\log n)$.
linear search: 1, 2, ... n comparisons
binary search: halve the remaining range each step
Exercises
Count comparisons in a linear search.
Classify three loops by growth.
Describe a memory-for-time trade-off.
Self-check
What does n represent?
Why ignore constants?
When is extra memory useful?
Self-Check Quiz
1. Which grows more slowly: $O(n)$ or $O(n^2)$?
Answer$O(n)$ grows more slowly for sufficiently large input.
2. Does Big-O give exact runtime?
AnswerNo. It describes growth, not machine-specific exact time.
Homework
Compare two algorithms for duplicate detection.
Estimate time and space growth.
Recommend one under a memory constraint.
Sample answerNested comparison is $O(n^2)$ time and constant extra space; a set-based method is typically $O(n)$ expected time and $O(n)$ space. Choose the set when memory is available and input is large.