Algorithm Efficiency and Big-O Notation

Definition

Why can a better method on an old laptop beat a worse method on a supercomputer?

Algorithm efficiency describes how the work an algorithm does grows as its input grows. Big-O notation gives that growth rate for the worst case, ignoring constant factors: O(1) is constant, O(log n) grows slowly, O(n) grows in step with the input, and O(n²) grows with the square of the input.

In simple words

Count steps, not seconds. Doubling the list doubles a linear search (O(n)) but adds just one step to binary search (O(log n)). Bubble sort on a list ten times longer takes about a hundred times as long (O(n²)). For big inputs, the growth rate matters far more than the speed of the computer.

Why it matters

AI works with millions of examples. An O(n²) step that is fine for 100 items can take days for a million. Big-O lets you predict this before running anything, and it is a standard topic in technical interviews.

How it works

Big-O	Name	Example	Steps for n = 1,000
O(1)	Constant	Look up a list item by index	1
O(log n)	Logarithmic	Binary search	≈ 10
O(n)	Linear	Linear search, summing a list	1,000
O(n log n)	Linearithmic	sorted()	≈ 10,000
O(n²)	Quadratic	Bubble sort, comparing every pair	1,000,000

The maths

Common growth rates, from slowest to fastest growing

O (1) < O (lo g n) < O (n) < O (n lo g n) < O (n^{2})

Binary search in the worst case

checks \approx ⌊ lo g_{2} n ⌋ + 1

$n$: The number of items in the sorted list
$lo g_{2} n$: How many times n can be halved before reaching 1

In code

Counting the worst-case work of three algorithms as the input grows.

big_o.py

import math

def linear_checks(n):
    return n                          # look at every item

def binary_checks(n):
    return math.floor(math.log2(n)) + 1

def bubble_comparisons(n):
    return n * (n - 1) // 2           # every pair, roughly

print(f"{'n':>9} {'linear':>9} {'binary':>7} {'bubble':>15}")
for n in [10, 100, 1000, 1000000]:
    print(f"{n:>9} {linear_checks(n):>9} {binary_checks(n):>7} {bubble_comparisons(n):>15}")

Output

        n    linear  binary          bubble
       10        10       4              45
      100       100       7            4950
     1000      1000      10          499500
  1000000   1000000      20    499999500000

Try it yourself

Which grows fastest?

Put each task under its Big-O growth rate.

Check every pair of students for a shared birthday
Add up all the numbers in a list
Find a name in a sorted phone book by halving
Get the first item of a list
Find the largest mark in an unsorted list

Common mistakes

Timing on tiny inputs and concluding that the method doesn't matter.
Thinking O(n) means exactly n steps. It describes how work grows, ignoring constants.
Forgetting that sorting first costs O(n log n).

Check yourself

1. Binary search is…

2. If n becomes 10 times bigger, an O(n²) algorithm does about…

3. Which matters most for very large inputs?

Summary

Efficiency is how work grows with input size.
Big-O: O(1) < O(log n) < O(n) < O(n log n) < O(n²).
For big data, choose the algorithm before buying a faster computer.

Finished reading?

Sources: W3Schools DSA: Time Complexity