Big-O notation
Also called: Time complexity, Space complexity
A way to describe how an algorithm's time or memory grows as the input gets bigger.
Definition
Big-O describes the growth rate of an algorithm, ignoring constants and small inputs. O(1) stays the same no matter the input size, O(n) grows in step with it, O(n²) grows with its square. Interviewers expect you to state both the time and the space complexity of your solution.
In practice
Checking a list for duplicates with two nested loops is O(n²); putting items in a hash set as you go is O(n).
Learn it in context
Lessons that use this term.