Big O Notation
Big O describes how run time grows with input size.
About this topic
Big O notation describes how an algorithm's running time or memory use grows as the input size n grows, ignoring small details and focusing on the biggest term. It lets us compare algorithms independent of the computer or programming language.
Common classes from best to worst are O(1) constant, such as reading an array item; O(log n), such as binary search; O(n), such as linear search; O(n log n), such as merge sort; O(n squared), such as bubble sort; and O(2 to the n), exponential, which becomes impractical very quickly. For n equal to 1,000, n squared is a million steps, but log n is only about 10. We drop constants and lower terms, so 3n plus 5 is O(n).
Think of finding a name in a phone book: reading every page is O(n) but halving the book repeatedly is O(log n). Big O is usually about the worst case unless stated. A common misconception is that it measures exact time in seconds; it only describes growth. Another is that a lower Big O is always faster for small inputs, but constant factors can matter. It guides choosing the right algorithm when data is large.
Key ideas
- O(1), O(log n), O(n), O(n²)
- Ignore constants
- Worst case focus
Quick check
Use cases: where Big O Notation helps
- Homework: review the key idea behind Big O Notation before you start a problem set.
- Exam revision: use the quick check to test whether you can recall Big O Notation without notes.
- Visual learning: play with the interactive lab to see how Big O Notation changes when you adjust its inputs.
- Teaching a friend: explain Big O Notation in your own words, then compare your version with the key ideas.
Computing ideas run phones, search engines, games and the wider internet.
Frequently asked questions
What is Big O Notation?
Big O describes how run time grows with input size.
What will I learn in Big O Notation?
O(1), O(log n), O(n), O(n²). Ignore constants. Worst case focus.
Is Big O Notation part of Computer Science?
Yes. It is one of 80 Computer Science topics on LearnViz HighSchoolEdu, with 3 key ideas, a live animation and a quick check.
Does the Big O Notation lab work on a phone or tablet?
Yes. The animation resizes to fit your screen and supports touch, so you can drag, tap and slide with your finger.
How should I study Big O Notation?
Read the summary and key ideas first, play with the interactive lab to see the idea in motion, then answer the quick check. If you get a question wrong, go back to the key idea it tests.
Do I need an account, and is my progress saved?
No account is needed. Marking a topic as learned is saved in your own browser, so it stays on that device and is not sent to a server.