I1 · Python Programming for AI

Algorithm Efficiency and Big-O Notation

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.

10 min Intermediate · Sublevel Beginner Jump to the activity

What you need: The earlier topics of this module.

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.

Overview

  • Efficiency describes how the time and memory an algorithm needs grow as the input size n grows.
  • Big-O notation gives an upper bound on that growth, ignoring constant factors and small terms.
  • It usually describes the worst case; best and average cases can also be stated.
  • Time complexity counts steps; space complexity counts extra memory.
  • Rules of thumb: a loop over n items is O(n); two nested loops are O(n²); halving each step is O(log n).
  • The difference matters hugely for big data: n² is a trillion steps when n is a million.

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.

Key terms

Time complexity
How the running time of an algorithm grows as the input grows.
Space complexity
How the memory an algorithm needs grows with the input.
Big-O notation
A way of writing the worst-case growth rate, ignoring constants, such as O(n).
Input size n
The quantity that grows, such as the number of items in a list.
Worst case
The input that makes the algorithm do the most work.
Scalability
Whether an approach still works when the data becomes very large.

Types

Algorithms fall into a small number of common growth classes. Here they are from fastest to slowest, with what each means in practice.

1. Constant time, O(1)

The work does not depend on the input size.

  • How it works: The algorithm does a fixed number of steps, whether the list has 10 items or 10 million.
  • Example: Reading marks[5], appending to a list, or looking up a key in a dictionary.
  • When to use it: Aim for it in operations repeated millions of times; use dictionaries and sets to get it.

2. Logarithmic time, O(log n)

The work grows very slowly, adding one step each time the input doubles.

  • How it works: The algorithm throws away a fixed fraction, usually half, of the remaining data at every step.
  • Example: Binary search: about 20 steps for a million items and 30 for a billion.
  • When to use it: Prefer it for searching large sorted data and for balanced tree structures.

3. Linear time, O(n)

The work grows in direct proportion to the input size.

  • How it works: The algorithm looks at each item a fixed number of times, usually once.
  • Example: Finding the maximum mark, summing a list or linear search.
  • When to use it: Expect it for any task that must read all the data at least once; it is usually the best possible for such tasks.

4. Linearithmic time, O(n log n)

Slightly more than linear: n times the logarithm of n.

  • How it works: Typical of divide-and-conquer algorithms that split the data log n times and do O(n) work at each level.
  • Example: Merge sort and Timsort: sorting a million items takes about 20 million steps.
  • When to use it: Accept it for sorting and similar tasks; it is the best possible for comparison-based sorting.

5. Quadratic time, O(n²)

The work grows with the square of the input size.

  • How it works: Usually caused by two nested loops over the data, comparing every item with every other.
  • Example: Bubble sort, or checking every pair of 10,000 students for duplicate phone numbers (about 50 million pairs).
  • When to use it: Avoid it for large inputs; a set or sorting often turns it into O(n) or O(n log n).

6. Exponential time, O(2ⁿ)

The work doubles with every extra input item.

  • How it works: Typical of trying every subset or every combination; 2⁵⁰ is over a thousand million million.
  • Example: Brute-force knapsack with n items, or naive recursive Fibonacci.
  • When to use it: Use it only for very small n; otherwise use dynamic programming, heuristics or genetic algorithms.

Explained in detail

Counting steps, not seconds

Timing a program with a stopwatch tells you how fast it ran on one computer with one input. Big-O notation answers a more useful question: how does the work grow as the input grows? It counts basic steps, keeps only the fastest-growing part and ignores constant factors. An algorithm that does 3n + 5 steps is O(n); one that does n² + 100n is O(n²), because for large n the n² term dominates. This lets you compare algorithms before writing them, and predict whether an approach will survive real data sizes.

The common classes

Big-ONameExamplen = 1,000,000
O(1)ConstantLooking up a dictionary key1 step
O(log n)LogarithmicBinary searchAbout 20 steps
O(n)LinearLinear search, summing a list1,000,000 steps
O(n log n)LinearithmicTimsort, merge sortAbout 20 million steps
O(n²)QuadraticBubble sort, comparing every pair1,000,000,000,000 steps
O(2ⁿ)ExponentialTrying every subsetImpossible

At a billion simple steps per second, the O(n²) row takes about a quarter of an hour; the O(n log n) row takes a fiftieth of a second. That gap, not the speed of your computer, decides what is practical.

Reading complexity from code

  • A single loop over n items is usually O(n).
  • A loop inside a loop, both over n, is usually O(n²).
  • Halving the problem each step gives O(log n).
  • Hidden loops count: x in a_list inside a loop makes O(n²), while x in a_set keeps it O(n).
  • Python's built-ins have known costs: list.append is O(1), list.insert(0, x) is O(n), sorted is O(n log n).

Why this matters for AI

AI works with huge data, so complexity decides what is possible. Comparing every pair of a million images is out of reach, which is why search engines and recommendation systems use special indexes. The attention mechanism in transformers is O(n²) in the length of the text, which is the main reason language models have context limits and why researchers work hard on cheaper alternatives. Knowing Big-O lets you understand these limits instead of being puzzled by them.

Big-O describes growth, not exact speed. For small inputs a simple O(n²) method can beat a clever O(n log n) one, so measure when it matters.

How it works

Big-ONameExampleSteps for n = 1,000
O(1)ConstantLook up a list item by index1
O(log n)LogarithmicBinary search≈ 10
O(n)LinearLinear search, summing a list1,000
O(n log n)Linearithmicsorted()≈ 10,000
O(n²)QuadraticBubble sort, comparing every pair1,000,000

The maths

Common growth rates, from slowest to fastest growing
Binary search in the worst case
The number of items in the sorted list
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

Question 1

1. Binary search is…

Question 2

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

Question 3

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