---
title: "Measures of efficiency with standard curves"
subject: "Data Structure and Algorithm"
chapter: 9
key: "semester_4/data_structure_and_algorithm:efficiency-measures-curve"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/efficiency-measures-curve
site: BCT Engineering
---

# Measures of efficiency with standard curves

Data Structure and Algorithm · Chapter 9: Growth Functions

- Asked in: 2068 Bhadra, 4 marks
- Video: [Learn Big O notation in 6 minutes 📈](https://www.youtube.com/watch?v=XMUe3zFhM5c) — Bro Code
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/efficiency-measures-curve
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-9

## Question

Illustrate measures of efficiency of algorithm with standard curve and problem size.

## 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.

## Answer

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):
```text
 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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What are the two measures of efficiency?
   A. Speed and colour
   B. Input and output
   C. Code length and comments
   D. Time complexity and space complexity
   Answer: D. Both are functions of n. (Key point: Measures)

2. Which growth order does binary search have?
   A. Logarithmic
   B. Linear
   C. Quadratic
   D. Constant
   Answer: A. log2 n. (Key point: Binary search)

3. Which algorithm is given as linearithmic?
   A. Bubble sort
   B. Merge sort
   C. Sequential search
   D. Array access
   Answer: B. Merge sort is n log n. (Key point: n log n)

4. Which order becomes impractical for large n?
   A. n log n
   B. n
   C. 2^n
   D. log n
   Answer: C. Exponential growth explodes. (Key point: Exponential)

## Related in Data Structure and Algorithm

- [Big-O and Big-Omega with curves](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abig-o-big-omega-curves) — Data Structure and Algorithm, chapter 9, asked 4×
- [TOH problem with solution for n disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-n-disks-solution) — Data Structure and Algorithm, chapter 5, asked 2×
- [TOH algorithm and recursion tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-algorithm-recursion-tree) — Data Structure and Algorithm, chapter 5, asked 2×
- [Recursion properties, Fibonacci, TOH algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-properties-fibonacci-toh) — Data Structure and Algorithm, chapter 5
- [Prefer O(n) or O(log n) algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aprefer-on-or-ologn) — Data Structure and Algorithm, chapter 9
- [Linear probing insertion into size-10 table](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ahash-linear-probing-62-37) — Data Structure and Algorithm, chapter 8

## Related in other subjects

- [Air standard diesel: efficiency and mean effective pressure](https://www.bctengineer.com/question.md?key=semester_2%2Ffundamental_of_thermodynamics_and_heat_transfer%3Adiesel-cycle-cutoff-2-efficiency-mep) — Fundamental of Thermodynamics & Heat Transfer, chapter 6
- [Air standard Brayton: state points, work, efficiency](https://www.bctengineer.com/question.md?key=semester_2%2Ffundamental_of_thermodynamics_and_heat_transfer%3Abrayton-0-18mpa-34c-max-2350) — Fundamental of Thermodynamics & Heat Transfer, chapter 6
- [Footing size from plate load test curve](https://www.bctengineer.com/question.md?key=semester_5%2Ffoundation_engineering%3Aplate-load-footing-size-3200kn) — Foundation Engineering, chapter 6
- [Aggregate size; well-graded from grading curve](https://www.bctengineer.com/question.md?key=semester_5%2Fconcrete_technology_and_masonry_structure%3Aaggregate-size-well-graded) — Concrete Technology and Masonry Structure, chapter 1