Complexity
Complexity: Time and space, stated plainly.
Get Big-O time and space complexity with the reasoning behind it and concrete rewrites that lower the cost.
1 line0 / 20,000js⌘↵ run
paste code, or load the sample
No bounds yet
Run the instrument to get time and space complexity, the reasoning behind the bound, and an optimised rewrite when one is worthwhile.
What this instrument does
Get the time and space complexity of a function in Big-O notation, the reasoning that produces that bound, and the single change that would most improve it.
The bound is only as good as the assumptions behind it, so the reasoning is never skipped. You can see which operation dominates, and why.
How it works
- Time and space are reported separately
- A function can be linear in time and quadratic in space, or the reverse. Reporting one number for both hides the tradeoff that usually matters when memory is the constraint.
- Nested loops are resolved, not guessed
- The analysis reasons about which loops are entered once, which scale with the input, and which scale with each other. Sequential loops multiply; loops over separate collections add.
- The rewrite is optional
- If the code is already close to optimal, no rewrite is produced. Padding the answer with a worse implementation to look productive is worse than saying nothing.
Questions about Complexity
Questions
- What does Big-O notation actually measure?
- It measures how an algorithm's cost grows as its input grows, discarding constants and lower-order terms. O(n) means cost grows linearly; O(n²) means quadratically; O(log n) means each additional step halves the remaining work. Constants are dropped because they stop mattering at scale: an O(n²) algorithm with a fast constant still loses to an O(n) one once the input is large enough.
- What is the difference between time and space complexity?
- Time complexity measures operations performed. Space complexity measures memory held at once, which includes both the input and any additional structures allocated. Recursion is usually where the two diverge: a recursive algorithm can be O(2ⁿ) time while holding only O(n) space on the call stack.
- Why does my function report O(n) when a loop is nested?
- Nested loops only multiply when both scale with the input. A loop that runs a fixed number of times inside an O(n) loop leaves the bound at O(n). A loop bounded by a constant, or one that exits early on the common path, may not contribute to the worst case at all.
- Does Big-O describe the average case?
- No. A single Big-O figure describes the worst case unless it is qualified. An algorithm with a worst case of O(n²) and an average case of O(n), such as quicksort on an already-sorted array, needs both figures stated to be described honestly.
All instruments
Other instruments