- 2068 Bhadra · 4 marks
Measures of efficiency with standard curves
Short answer
Efficiency is measured by time and space complexity vs. input size n. Standard growth orders include O(1), O(log n), O(n), O(n log n), O(n²), O(n³), and O(2ⁿ). Slower growth curves (e.g., log n) represent efficient algorithms; quadratic and exponential become impractical for large n.
Illustrate measures of efficiency of algorithm with standard curve and problem size.
The efficiency of an algorithm is measured by two things as a function of the problem size n:
- Time complexity: number of basic operations (steps) executed.
- Space complexity: extra memory needed.
Each is expressed by its growth rate with n. The standard orders of growth are:
| Order | Name | n = 10 | n = 100 | n = 1000 | Example |
|---|---|---|---|---|---|
| 1 | Constant | 1 | 1 | 1 | array access |
| log₂ n | Logarithmic | 3.3 | 6.6 | 10 | binary search |
| n | Linear | 10 | 100 | 1,000 | sequential search |
| n log₂ n | Linearithmic | 33 | 664 | 9,966 | merge sort |
| n² | Quadratic | 100 | 10,000 | 10⁶ | bubble sort |
| n³ | Cubic | 1,000 | 10⁶ | 10⁹ | matrix multiplication |
| 2ⁿ | Exponential | 1,024 | 1.3×10³⁰ | huge | subset enumeration |
Curves (time against n):
time
| 2^n
| / n^2
| / / n log n
| / / / . n
| / / /.' .
| / / /.' .'
| _/_/_.-'.-' ___ log n
| _____--''-----'------------ 1
|________________________________ n
Slower-growing curves (1, log n, n) show efficient algorithms; steeply rising ones (n², 2ⁿ) become impractical for large n.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Big-O and Big-Omega with curves · Data Structure and Algorithm, chapter 9 · asked 4×
- TOH problem with solution for n disks · Data Structure and Algorithm, chapter 5 · asked 2×
- TOH algorithm and recursion tree · Data Structure and Algorithm, chapter 5 · asked 2×
- Recursion properties, Fibonacci, TOH algorithm · Data Structure and Algorithm, chapter 5
- Prefer O(n) or O(log n) algorithm · Data Structure and Algorithm, chapter 9
- Linear probing insertion into size-10 table · Data Structure and Algorithm, chapter 8
- Air standard diesel: efficiency and mean effective pressure · Fundamental of Thermodynamics & Heat Transfer, chapter 6
- Air standard Brayton: state points, work, efficiency · Fundamental of Thermodynamics & Heat Transfer, chapter 6
- Footing size from plate load test curve · Foundation Engineering, chapter 6
- Aggregate size; well-graded from grading curve · Concrete Technology and Masonry Structure, chapter 1