Practise Big-O & Complexity Analysis one question at a time. Answer out loud or in writing, get graded, and see exactly what you missed.
What is Big-O notation and what problem does it solve?
Big-O notation describes how an algorithm's work grows as its input gets larger. It ignores machine speed and focuses on the shape of that growth.
The problem it solves is fair comparison. A fast laptop can make a bad algorithm look quick on tiny inputs. Big-O strips away hardware and fixed setup, so you see which method wins once data gets big.
You also use it to predict scaling. Say your report takes one second on a thousand rows. Big-O tells you whether a million rows means minutes or days.
Missed:
“So these describe how the work grows as the input gets bigger. O(1) is constant time - it doesn't matter if you have ten items or ten million, like grabbing an array element by its index or looking up a key in a hash map. O(n) is linear, so if you double the input you roughly double the work, like looping once through a list to find the biggest number. O(log n) is when you keep cutting the problem in half, like binary search, so even a million items only takes around twenty steps. And O(n^2) usually comes from nested loops, like checking every pair of items for duplicates, so doubling the input makes it about four times slower.”
Knew itCovers all four classes correctly with good examples and the right growth relationships. Missing the general principle that each class names how time reacts to doubling the input, not just isolated descriptions.
Missed: Doesn't state the unifying frame that each class describes how runtime reacts when input doubles
Missed: Doesn't mention why the gap between classes matters more than micro-optimizing code
Get your own answers graded
Sign up free. Your account comes with 50 credits for grading, and it remembers what you missed.
What it covers
All 57 questions
Big-O notation basics
What Big-O measures and why, best, average and worst case, time versus space, dropping constants, and the O, Theta and Omega bounds.
- What is Big-O notation and what problem does it solve?
- What is the difference between best, average, and worst case complexity?
- What is the difference between time complexity and space complexity?
- Why do we drop constants and lower-order terms in Big-O?
- What is the difference between Big-O, Big-Theta, and Big-Omega notation? Pro
Growth rates and complexity classes
The common growth rates and what they mean, why halving gives log n, why n log n is so common, and what P, NP and NP-complete mean.
- What do O(1), O(n), O(log n), and O(n^2) mean in plain terms?
- What are the common growth rates ordered from fastest to slowest?
- Why does repeatedly halving the input produce logarithmic time? Pro
- Why does the base of a logarithm not matter in Big-O? Pro
- Why do so many efficient algorithms land at O(n log n)? Pro
- What do P, NP, and NP-complete mean, and why do they matter in practice? Pro
Analyzing loops and code
Working out the cost of real code: single and nested loops, adding versus multiplying, two-variable bounds and hidden costs in strings and library calls.
- How do you work out the time complexity of a simple loop?
- How do you find the time complexity of two nested loops? Pro
- When do you add complexities together and when do you multiply them? Pro
- When should you describe complexity with two variables like O(n + m)? Pro
- Why does string concatenation inside a loop often cost O(n^2)? Pro
- How do hidden costs of library functions distort your analysis? Pro
Data structure operation costs
The costs of operations on arrays, linked lists, hash tables, trees, heaps and graphs, and what makes those costs degrade.
- What are the time complexities of the basic array operations? Pro
- Why is hash table lookup usually O(1), and what makes it slower? Pro
- How does a linked list's complexity compare to an array's for common operations? Pro
- When is a hash table a worse choice than a balanced tree? Pro
- How does an unbalanced tree degrade a binary search tree's operation costs? Pro
- What are the time complexities of the core heap operations, and why? Pro
- Why is graph traversal O(V + E) rather than O(V^2)? Pro
- Why can crafted keys force a hash table to O(n), and how do randomized seeds help? Pro
Recursion and recurrences
Deriving the running time of recursive code with recurrences and the master theorem, and spotting and fixing exponential blowup with memoization.
Amortized and expected cost
Amortized analysis, dynamic array resizing, how amortized differs from average and expected time, and the latency cost of rare expensive operations.
- What is amortized analysis and when does it apply? Pro
- Why is appending to a dynamic array O(1) amortized despite resizing? Pro
- What is the difference between amortized and average-case complexity? Pro
- How does a randomized algorithm's expected time differ from average-case time? Pro
- Why is amortized O(1) not good enough for a latency-sensitive system? Pro
- How do you keep a hash table resize from causing a latency spike? Pro
- Why does preallocating capacity change the amortized cost of bulk insertion? Pro
Space complexity and tradeoffs
Trading memory for time, the stack cost of deep recursion, recursion versus iteration, constant-space streaming and probabilistic structures.
- What is a space-time tradeoff, with a concrete example? Pro
- What is the space cost of deep recursion, and when does the stack overflow? Pro
- How does converting recursion to iteration change space complexity? Pro
- How do you analyze an algorithm that processes a stream in constant space? Pro
- When is it worth trading exact answers for space with a probabilistic structure? Pro
Constant factors and hardware
Where Big-O misleads in practice: cache behavior, memory layout, small inputs, huge hidden constants, and measuring the real constant yourself.
- Why can an O(n) array scan beat an O(n) linked list in practice? Pro
- When is an O(n^2) algorithm actually faster than an O(n log n) one? Pro
- How can an excellent Big-O hide a constant factor that makes it unusable? Pro
- Why do cache misses often dominate runtime more than raw operation count? Pro
- How do you empirically verify the constant factors that Big-O ignores? Pro
Complexity at scale
How analysis changes for data beyond memory, billions of elements, sharded systems, concurrency and parallel work.
- What breaks in your complexity reasoning once data exceeds memory? Pro
- How does the external-memory IO model change which algorithm wins? Pro
- What does making a data structure thread-safe cost in complexity terms? Pro
- What changes in your analysis scaling from a million to a billion elements? Pro
- How do you reason about complexity across a sharded, distributed system? Pro
- When does parallelism reduce complexity and when does it just add overhead? Pro
More questions
- How do you use the input constraints in a problem to decide which complexity class is fast enough? Pro
- What are the time and space complexities of the common sorting algorithms, and when does each one win? Pro
- Why is the O(nW) knapsack dynamic program called pseudo-polynomial rather than polynomial? Pro
- What does it mean for a problem to be NP-complete, and how is that different from an algorithm merely being slow? Pro
- Why can no comparison-based sort beat O(n log n), and how do counting and radix sort get around that bound? Pro
All questions
Showing of 57What is Big-O notation and what problem does it solve?
Answer it yourself first - out loud, or typed below.
How should your speech become text?
Listening… your words appear above as you speak - tap Stop when you're done.
Recording · cr - tap Stop & transcribe when you're done.
Transcribing with AI…
Voice:
Last attempt -
Big-O notation describes how an algorithm's work grows as its input gets larger. It ignores machine speed and focuses on the shape of that growth.
The problem it solves is fair comparison. A fast laptop can make a bad algorithm look quick on tiny inputs. Big-O strips away hardware and fixed setup, so you see which method wins once data gets big.
You also use it to predict scaling. Say your report takes one second on a thousand rows. Big-O tells you whether a million rows means minutes or days.
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
Why there's no diagram: “”
The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓
What do O(1), O(n), O(log n), and O(n^2) mean in plain terms?
Answer it yourself first - out loud, or typed below.
How should your speech become text?
Listening… your words appear above as you speak - tap Stop when you're done.
Recording · cr - tap Stop & transcribe when you're done.
Transcribing with AI…
Voice:
Last attempt -
Each class names how the running time reacts when you double the input.
O(1)constant: the cost stays the same no matter the size. Reading one array slot by its index never gets slower.O(n)linear: cost grows in step with size. Scanningnitems takes twice as long whenndoubles.O(log n)logarithmic: doubling the input adds just one more step. Binary search on sorted data behaves this way.O(n^2)quadratic: cost grows with the square. Comparing every pair quadruples when the list doubles.
The gaps between these decide real performance. At a million items, O(log n) is about twenty steps while O(n^2) is a trillion. That difference is why picking the right class matters more than any small code tweak.
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
Why there's no diagram: “”
The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓
What is the difference between best, average, and worst case complexity?
Answer it yourself first - out loud, or typed below.
How should your speech become text?
Listening… your words appear above as you speak - tap Stop when you're done.
Recording · cr - tap Stop & transcribe when you're done.
Transcribing with AI…
Voice:
Last attempt -
Best, average, and worst case describe one algorithm running on different inputs. Worst case is the slowest an input can make it. Best case is the luckiest input. Average case is what you expect over typical data.
Take searching an unsorted list for a value. Best case, it sits first, so O(1). Worst case, it sits last or is missing, so O(n). Average case lands around the middle, still O(n).
You usually plan around worst case because no input can make the algorithm run slower than that. Best case is often useless for guarantees. Average case matters when you know the data behaves normally and rare slow inputs are acceptable in your system.
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
Why there's no diagram: “”
The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓
What is the difference between time complexity and space complexity?
Answer it yourself first - out loud, or typed below.
How should your speech become text?
Listening… your words appear above as you speak - tap Stop when you're done.
Recording · cr - tap Stop & transcribe when you're done.
Transcribing with AI…
Voice:
Last attempt -
Time complexity measures how many operations an algorithm performs. Space complexity measures how much extra memory it needs while running. Both are measured against input size, but they answer different questions about cost.
Consider summing an array. You touch each element once, so time is O(n). You only keep one running total, so extra space is O(1). The two numbers move independently of each other.
They often trade against each other. A lookup table can make code faster while using more memory. Knowing both matters because a program can be quick yet crash by exhausting RAM, or use little memory yet run far too slowly.
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
Why there's no diagram: “”
The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓
How do you work out the time complexity of a simple loop?
Answer it yourself first - out loud, or typed below.
How should your speech become text?
Listening… your words appear above as you speak - tap Stop when you're done.
Recording · cr - tap Stop & transcribe when you're done.
Transcribing with AI…
Voice:
Last attempt -
Count how many times the loop body runs as the input grows. A loop that visits every one of n items runs n times. If each pass does a fixed amount of work, the loop is O(n).
for (let i = 0; i < n; i++) {
total += arr[i]; // runs n times, O(1) each
}
// whole loop: O(n)
The loop bound is what matters, not the constant work inside. A loop from zero to n stays O(n) even if the body does ten small steps.
Look at what the counter depends on. If it runs a fixed number of times regardless of input, that part is O(1). A bound that grows differently, like stopping at the square root of n, changes the class.
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
Why there's no diagram: “”
The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓
Why do we drop constants and lower-order terms in Big-O?
Answer it yourself first - out loud, or typed below.
How should your speech become text?
Listening… your words appear above as you speak - tap Stop when you're done.
Recording · cr - tap Stop & transcribe when you're done.
Transcribing with AI…
Voice:
Last attempt -
Big-O drops constants and lower-order terms because it tracks growth shape, not exact operation counts. Multiplying by two or adding a fixed setup does not change how a curve bends as the input grows.
Say an algorithm does 3n + 100 steps. For small n the hundred dominates. But as n reaches millions, the 3n term outweighs it, and the factor three does not change that it grows linearly. So the algorithm is O(n).
This makes comparisons hardware-free. A constant might just come from one machine being faster. By ignoring it, Big-O shows which algorithm pulls ahead as the problem gets large, on any computer.
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
Why there's no diagram: “”
The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓
What are the common growth rates ordered from fastest to slowest?
Answer it yourself first - out loud, or typed below.
How should your speech become text?
Listening… your words appear above as you speak - tap Stop when you're done.
Recording · cr - tap Stop & transcribe when you're done.
Transcribing with AI…
Voice:
Last attempt -
The common growth rates run from O(1) at the cheap end to O(n!) at the expensive end. Each class in this list costs more than the one above it as input grows:
O(1)constant: same cost always, like a hash lookup.O(log n)logarithmic: binary search on sorted data.O(n)linear: one scan through the data.O(n log n)linearithmic: the best general sorting.O(n^2)quadratic: comparing every pair.O(2^n)exponential: trying every subset.O(n!)factorial: trying every ordering.
"Fastest" here means it grows slowest, so it stays cheap at scale.
At a thousand items, linear is a thousand steps while quadratic is a million. Anything exponential or factorial becomes unusable past small inputs, so spotting it early saves you from a program that never finishes.
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
Why there's no diagram: “”
The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓
What is the difference between Big-O, Big-Theta, and Big-Omega notation?
How do you find the time complexity of two nested loops?
Why does repeatedly halving the input produce logarithmic time?
What are the time complexities of the basic array operations?
Why is hash table lookup usually O(1), and what makes it slower?
When do you add complexities together and when do you multiply them?
How do you derive the running time of a recursive function?
What is the master theorem and when can you apply it?
How does memoization change the complexity of recursive Fibonacci?
What is amortized analysis and when does it apply?
Why is appending to a dynamic array O(1) amortized despite resizing?
What is the difference between amortized and average-case complexity?
When should you describe complexity with two variables like O(n + m)?
How does a linked list's complexity compare to an array's for common operations?
When is a hash table a worse choice than a balanced tree?
How does an unbalanced tree degrade a binary search tree's operation costs?
What are the time complexities of the core heap operations, and why?
Why is graph traversal O(V + E) rather than O(V^2)?
Why does the base of a logarithm not matter in Big-O?
Why do so many efficient algorithms land at O(n log n)?
What is a space-time tradeoff, with a concrete example?
Why does string concatenation inside a loop often cost O(n^2)?
How do hidden costs of library functions distort your analysis?
How does a randomized algorithm's expected time differ from average-case time?
What do P, NP, and NP-complete mean, and why do they matter in practice?
How do you spot accidental exponential blowup in recursive branching?
How do you use the input constraints in a problem to decide which complexity class is fast enough?
What are the time and space complexities of the common sorting algorithms, and when does each one win?
Why can an O(n) array scan beat an O(n) linked list in practice?
When is an O(n^2) algorithm actually faster than an O(n log n) one?
How can an excellent Big-O hide a constant factor that makes it unusable?
Why is amortized O(1) not good enough for a latency-sensitive system?
Why can crafted keys force a hash table to O(n), and how do randomized seeds help?
What breaks in your complexity reasoning once data exceeds memory?
How does the external-memory IO model change which algorithm wins?
What is the space cost of deep recursion, and when does the stack overflow?
How does converting recursion to iteration change space complexity?
How do you keep a hash table resize from causing a latency spike?
What does making a data structure thread-safe cost in complexity terms?
How do you analyze an algorithm that processes a stream in constant space?
When is it worth trading exact answers for space with a probabilistic structure?
Why do cache misses often dominate runtime more than raw operation count?
What changes in your analysis scaling from a million to a billion elements?
How do you reason about complexity across a sharded, distributed system?
Why does preallocating capacity change the amortized cost of bulk insertion?
When does parallelism reduce complexity and when does it just add overhead?
How do you empirically verify the constant factors that Big-O ignores?
Why is the O(nW) knapsack dynamic program called pseudo-polynomial rather than polynomial?
What does it mean for a problem to be NP-complete, and how is that different from an algorithm merely being slow?
Why can no comparison-based sort beat O(n log n), and how do counting and radix sort get around that bound?
This answer is part of Pro.
The full written answer, with the trade-offs and follow-ups an interviewer will probe.
No matches
Try a different filter or search term.
Big-O & Complexity Analysis in pictures.
A quick recap of Big-O & Complexity Analysis in 32 short animated pictures, one idea at a time. About 8 min to get the whole topic back in your head before you walk in. Pause any picture, slow it down, or step through it.
Pro The first chapter is free to play. The other 27 pictures come with Pro.
Big-O & Complexity Analysis cheatsheet
- What Big-O means01
- Counting steps in code02
- Recursion & sorting03
- Data structure costs04
- Amortized cost05
- Space & the call stack06
- Constants, caches & disks07
- Threads, cores & shards08
- The model09
- + 3 more inside
This picture is part of Pro. The first chapter is free to play; the other 27 pictures come with Pro.
Get Pro · $10/mo Already Pro? Sign in50 of 57 Big-O & Complexity Analysis answers are in Pro.
Full answers, code samples, and AI explanations that go simpler or deeper. Cancel anytime.
- Full answers + code
- AI explanations, simpler or deeper
- 1,000 AI credits / month
- Cancel anytime
Change topic
Pick a different technology or stack. Your current topic stays put until you choose a new one.
MEAN
MongoDB, Express, Angular, Node.jsMERN
MongoDB, Express, React, Node.jsDjango
Python Full-Stack DevelopmentRuby on Rails
Convention over ConfigurationServerless on AWS
Serverless Architecture on AWSInterviewers also test these - they're common to every stack, whichever one you picked above.
Flutter Mobile
Flutter Cross-Platform Mobile DevelopmentInterviewers also test these - they're common to every stack, whichever one you picked above.
Spring Boot
Enterprise Java Development.NET
Microsoft EcosystemVue
Vue.js, Vite, TypeScript, Tailwind, Node.jsGo Backend
Golang, gRPC, PostgreSQL, Redis, RabbitMQInterviewers also test these - they're common to every stack, whichever one you picked above.
FastAPI
Python, FastAPI, SQLAlchemy, PostgreSQLReact Native
React, TypeScript, Redux, FirebaseiOS Native
Swift, SwiftUI, UIKit, FirebaseAndroid Native
Java, Jetpack Compose, FirebaseDevOps / Platform
Docker, Kubernetes, Terraform, CI/CDInterviewers also test these - they're common to every stack, whichever one you picked above.
AI Engineer
LLMs, RAG, Agents, EvalsAI-Powered Developer
Claude Code, Copilot, Agentic WorkflowsCore SWE Interview Prep
Data structures, algorithms, OS, concurrency, networking, gitInterviewers also test these - they're common to every stack, whichever one you picked above.
Interviewers also test these - they're common to every stack, whichever one you picked above.