Practice Flashcards
Flip to reveal answersWhat does Big O describe?
Track your progress — Sign up free to save your progress and get smart review reminders based on spaced repetition.
All 5 Flashcards — Big O notation
Sign up free to track progress and get spaced-repetition review schedules.
Question
What does Big O describe?
Answer
How an algorithm's work grows as the data grows — the shape of the growth, not the time in seconds, which depends on the machine it runs on.
Question
How do you work out an algorithm's complexity?
Answer
Count the loops over the data. No loop is O(1), one loop is O(n), a loop inside a loop is O(n²), and halving what is left at each step is O(log n).
Question
Why is 2n + 5 written as O(n)?
Answer
Big O describes the shape of the growth, and constants and lower-order terms do not change that shape. Doubling the data still doubles the work.
Question
What is the difference between time and space complexity?
Answer
Time complexity is how the number of steps grows; space complexity is how the extra memory grows, not counting the input. Bubble sort is O(n²) time but O(1) space, because it sorts in place.
Question
What does O(n²) mean in practice?
Answer
Twice the data means four times the work, and ten times the data means a hundred times. At 1,000 items that is a million steps; at 10,000 it is a hundred million.
Read the notes
Full study notes for Big O notation
Topic 6.4 hub
Programming algorithms
More from Topic 6.4
All flashcards in this topic
Computer Science exam skills
Paper structures & tips
Track your progress with spaced repetition
Sign up free — Aimnova tells you exactly which cards to review and when, so you remember everything before your IB exam.
Start Free