Big-O Notation: How Fast Is Your Code?
Every algorithm you will ever write has a cost: time to run and memory to hold its data. Big-O notation is the language programmers use to describe that cost, and it is the single most common topic in technical interviews. In this lesson you will learn to read Big-O, measure it in real Python code, and recognize the handful of complexity classes that cover almost everything you will meet in practice.
What You'll Learn
- What Big-O notation actually measures (and what it ignores)
- The common complexity classes: O(1), O(log n), O(n), O(n log n), O(n^2)
- How to analyze a Python function line by line
- How to time real code and watch complexity appear in the numbers
Why We Need Big-O
Suppose two functions both find the largest number in a list. One checks every element once. The other compares every element with every other element. Both give the right answer, but on a list of one million items the first does one million steps and the second does one trillion. Big-O captures that difference without caring about your laptop's speed.
Big-O describes how the number of steps grows as the input grows. Constants and small terms are dropped: an algorithm doing 3n + 5 steps is simply O(n), because for large inputs the n dominates.
The Common Complexity Classes
| Big-O | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing my_list[3] |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Scanning a list once |
| O(n log n) | Linearithmic | Merge sort, Python's sorted() |
| O(n^2) | Quadratic | Comparing all pairs, bubble sort |
| O(2^n) | Exponential | Naive recursive Fibonacci |
Run the code below to see how quickly these grow apart:
At n = 10000, an O(log n) algorithm does about 13 steps while an O(n^2) algorithm does 100 million. That gap is why complexity matters more than any micro-optimization.
Analyzing Code: Count the Loops
The practical skill is reading a function and spotting how work scales with input size:
Rules of thumb:
- A single loop over the input is O(n)
- A loop inside a loop over the same input is O(n^2)
- Halving the problem each step (binary search) is O(log n)
- Doing O(n) work at each of O(log n) levels (merge sort) is O(n log n)
- Sequential blocks add, and you keep only the biggest term: O(n) followed by O(n^2) is O(n^2)
Watch Complexity in Real Timings
Theory is nice, but you can measure it. This experiment times a linear and a quadratic duplicate-checker as the input doubles. Open it fullscreen with the expand button and experiment with the sizes:
Notice the pattern: when n doubles, the quadratic time roughly quadruples while the linear time roughly doubles. That is Big-O showing up in real milliseconds, and it is the same trade you will make again and again in this course: a smarter data structure (here, a set) turns O(n^2) into O(n).
Space Complexity
Big-O also describes memory. has_dup_quadratic uses O(1) extra space (just two loop counters), while has_dup_linear uses O(n) extra space for the set. Trading memory for speed is one of the most common patterns in algorithm design.
Exercises
Key Takeaways
- Big-O describes how running time or memory grows with input size, ignoring constants
- The classes to know: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n)
- Nested loops over the same input usually mean O(n^2); one pass means O(n)
- Choosing a better data structure (like a set for membership tests) often improves the complexity class itself
- Space complexity matters too, and trading memory for speed is a standard technique
اختبار قصير
التالي · الدرس 2 من 11
Arrays and Python Lists Under the Hood
قراءة 3 دقيقة
أنهيت 1 من 11 درسًا

اسأل Byte عن هذا الدرس
محادثة خاصة حول هذا الدرس. قرأ Byte الدرس كاملًا، ويجيب خلال ثوانٍ، ويُظهر القسم الذي تأتي منه كل إجابة. يمكنك السؤال بأي لغة.
الأسئلة والأجوبة
أسئلة عامة حول هذا الدرس. يجيب AI Tutor فورًا بلغتك، ويراجع فريق FreeAcademy الإجابات، ويمكن لكل المتعلمين قراءتها.

