Programs must not only be correct; they must also be efficient. A program that produces the right answer in a thousand years is useless, and a program that takes seconds for a small input but days for a realistic input cannot serve real users. The idea of efficiency is the systematic study of how the time and memory used by a program grow as the size of its input grows. It is the discipline that lets a programmer predict whether a solution will scale.
The central tool of this analysis is complexity. Instead of measuring seconds, which depend on the machine and the language, complexity counts the number of basic operations as a function of the input size n, and then describes how that count grows. Big-O notation, written O(n), O(n^2) or O(log n), classifies growth rates so algorithms can be compared independently of hardware. A linear search on a million items costs a million steps; a binary search costs about twenty. That difference is the whole subject.
This chapter introduces the motivation for efficiency, explains how to count operations and express complexity in Big-O notation, compares common growth rates, and analyses the complexity of the algorithms studied earlier in the course, including searching, sorting, stack and queue operations, and recursion. It also discusses time versus space trade-offs and gives practical guidance on measuring and improving performance.
Consider a sorting program. For an input of 10 elements, an O(n^2) algorithm needs about 100 operations and finishes instantly; for 1,000,000 elements it needs about 10^12 operations and takes hours or days. A well-designed O(n log n) merge sort needs only about 20 million operations and finishes in seconds. As data grows to millions of records, the difference between algorithms becomes enormous, dwarfing machine speed.
Efficiency also matters for user experience, cost and feasibility. Websites must answer queries in milliseconds; mobile devices have limited memory; and real-time systems must meet strict deadlines. Complexity analysis tells the programmer, before writing a single line, whether an approach can possibly work at the required scale, and it guides the choice between alternatives.
import time
def measure(n):
start = time.time()
total = 0
for i in range(n):
total += i
return time.time() - start
print("Time for 1e6:", round(measure(10**6), 4), "seconds")
To compare algorithms fairly, the analysis counts the number of fundamental operations, such as comparisons or assignments, as a function of the input size n. Constants and machine details are ignored, and only the dominant term matters.
# This loop performs about n operations
def sum_list(lst):
total = 0
for x in lst:
total += x
return total
# This nested loop performs about n*n operations
def count_pairs(lst):
n = len(lst)
count = 0
for i in range(n):
for j in range(n):
count += 1
return count
The first function runs in linear time; the second runs in quadratic time. Doubling the input doubles the first, but quadruples the second.
Big-O notation gives an upper bound on the growth of an algorithm's time or space requirement. If an algorithm performs at most c x f(n) operations for some constant c and all sufficiently large n, its complexity is O(f(n)). The notation drops constant factors and lower-order terms: an algorithm doing 3n + 50 operations is O(n), and one doing 2n^2 + 5n + 100 operations is O(n^2).
Common growth rates, from slowest to fastest:
import math
def growth_table(n):
print("n:", n)
print("O(1): 1")
print("O(log n):", round(math.log2(n)))
print("O(n):", n)
print("O(n log n):", round(n * math.log2(n)))
print("O(n^2):", n * n)
growth_table(1000)
Linear search checks up to n elements, so its worst case is O(n) and its best case O(1). Binary search halves the range each step, giving O(log n) time in all cases and O(1) space for the iterative version. The superiority of binary search on large sorted data is the classic efficiency lesson.
Bubble sort and selection sort both run in O(n^2) time, with bubble sort's best case O(n) only when optimised and the data already sorted. Insertion sort runs in O(n) on nearly sorted data. Merge sort guarantees O(n log n) time in every case at the cost of O(n) extra space for merging. The trade-off between time and space is clearly visible here: merge sort trades memory for speed.
The list-based stack operations append and pop run in O(1) amortised time. Queue operations using append are O(1), but dequeue with pop(0) is O(n) because elements shift; collections.deque gives O(1) on both ends. Choosing the right implementation is itself an efficiency decision.
Factorial and power recursion perform one recursive call per level, giving O(n) time and O(n) stack space. The naive Fibonacci recursion branches exponentially, O(2^n) time, while the iterative or memoised version runs in O(n). Recursion's overhead means deeply recursive solutions may also hit the recursion depth limit.
Efficiency has two dimensions: time complexity and space complexity. Some algorithms trade one for the other. Merge sort uses O(n) extra space to achieve O(n log n) time. Memoization in recursion uses a dictionary of stored results to avoid exponential recomputation, again trading space for time. A good engineer balances both according to the constraints of the problem: memory may be plentiful while time is critical, or vice versa.
memo = {0: 0, 1: 1}
def fib_memo(n):
if n not in memo:
memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
return memo[n]
The memo dictionary stores up to n results, using O(n) space to bring the time from O(2^n) down to O(n).
Big-O analysis predicts asymptotic behaviour, but practical measurement confirms it. The time module and Python's timeit module measure execution time. Profilers identify which parts of a program consume the most time. Simple optimisations that respect the analysis include choosing efficient data structures, avoiding redundant work, using list comprehension instead of loops where appropriate, and keeping operations inside the algorithm's dominant term small.
import timeit
lst = list(range(10000))
time_append = timeit.timeit("sum([x*2 for x in lst])", globals=locals(), number=100)
print("Approximate time:", round(time_append, 4), "seconds")
The most important principle is that no amount of micro-optimisation can fix an algorithm with the wrong growth rate. Choosing an O(n log n) sort over an O(n^2) sort changes results at scale far more than any constant-factor tweak.
| Notation | Name | Example Algorithm |
|---|---|---|
| O(1) | Constant | Access list element by index |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search, factorial |
| O(n log n) | Linearithmic | Merge sort |
| O(n^2) | Quadratic | Bubble, selection sort |
| O(2^n) | Exponential | Naive Fibonacci |
| Algorithm | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) |
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
The idea of efficiency is the bridge between a correct program and a useful program. Big-O notation gives a precise, machine-independent vocabulary for describing how time and memory grow with input size, and it separates the algorithms that scale from those that do not. The course's algorithms now fit into a clear framework: linear and binary search contrast O(n) with O(log n); the simple sorts struggle at O(n^2) while merge sort achieves O(n log n) with extra space; stacks and queues offer O(1) operations when implemented well; and recursion teaches both the elegance of divide-and-conquer and the dangers of exponential recomputation. Choosing the right algorithm, and the right data structure, is the essence of computer science. This completes the Class 12 Computer Science journey, from the fundamentals of Python to the principles that govern efficient computation.