Computer Science
Grade 9
20 min
Big O Notation
Big O Notation
Tutorial Preview
1
Introduction & Learning Objectives
Learning Objectives
Define Big O notation and explain its purpose in measuring algorithm efficiency.
Identify the input size 'n' for a given simple algorithm.
Determine the time complexity for algorithms with constant O(1), linear O(n), and quadratic O(n^2) performance.
Compare the scalability of different algorithms based on their Big O complexity.
Analyze simple code snippets containing single loops or nested loops to find their Big O notation.
Explain why constant factors and non-dominant terms are removed when determining Big O.
Imagine you have to find a friend's name in a phone book versus a giant, unorganized pile of papers. Which would be faster and why? 🤔
Big O notation is a way to describe how fast an algorithm is, not in seconds, but in how its ru...
2
Key Concepts & Vocabulary
TermDefinitionExample
AlgorithmA set of step-by-step instructions that a computer follows to solve a problem or complete a task.A recipe to bake a cake is an algorithm. In programming, an algorithm could be the steps to sort a list of numbers from smallest to largest.
Time ComplexityA measure of how much time an algorithm takes to run as the size of its input increases. We don't measure this in seconds, but in the number of operations performed.If you have a list of 10 numbers, an algorithm might take 10 steps. If you have 100 numbers, it might take 100 steps. Its time complexity grows with the input size.
Big O NotationA mathematical notation used to describe the worst-case scenario for an algorithm's time or space complexity. It tells us how the performance of an algorithm cha...
3
Core Syntax & Patterns
Rule 1: Drop Constants
O(2n) becomes O(n). O(100) becomes O(1).
Big O notation focuses on the overall growth trend. A constant multiplier (like the '2' in '2n') doesn't change the fundamental growth shape, so we simplify by removing it.
Rule 2: Drop Non-Dominant Terms
O(n² + n) becomes O(n²). O(n + 1) becomes O(n).
We only care about the term that grows the fastest as 'n' gets very large. The n² term will grow so much faster than the 'n' term that the 'n' term's contribution becomes insignificant. We keep only the 'dominant' term.
Rule 3: Identify 'n'
'n' represents the size of the input.
Before analyzing an algorithm, always ask: 'What is the input, and how do we measure i...
4 more steps in this tutorial
Sign up free to access the complete tutorial with worked examples and practice.
Sign Up Free to ContinueSample Practice Questions
Challenging
An algorithm consists of two main parts that run one after the other. The first part sorts a list, which takes O(n²) time. The second part prints each item in the sorted list, which takes O(n) time. What is the overall Big O complexity of the entire algorithm?
A.O(n³)
B.O(n²)
C.O(n² + n)
D.O(n)
Challenging
What is the Big O time complexity of the following Python code, where `n` is a positive integer?
for i in range(n):
for j in range(5):
print(i, j)
A.O(n²)
B.O(5n)
C.O(n)
D.O(1)
Challenging
For a very small input, like n=3, an O(n²) algorithm might run faster in actual seconds than an O(n) algorithm due to having simpler operations. Why is Big O notation still the standard way to compare them?
A.Big O is only for theoretical computer science and has no practical use.
B.The O(n) algorithm must have a bug if it's slower.
C.It's a rule that O(n) is always better than O(n²), regardless of the input size.
D.Big O describes asymptotic behavior, focusing on how algorithms perform as 'n' approaches infinity, which is crucial for scalability.
Want to practice and check your answers?
Sign up to access all questions with instant feedback, explanations, and progress tracking.
Start Practicing Free