All questions
Showing of 53What 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. This lets you compare two approaches without running either on a specific computer.
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 use it to predict scaling. If a report takes one second on a thousand rows, Big-O tells you whether a million rows means minutes or days. That decides whether your design survives real traffic instead of collapsing under it.
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. Scanning n items takes twice as long when n doubles.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 it bounds the pain. 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 grow with 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 eating more memory. Knowing both matters because a program can be quick yet crash by exhausting RAM, or thrifty yet far too slow to use.
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 -
We drop constants and lower-order terms because Big-O tracks growth shape, not exact operation counts. Multiplying by two or adding a fixed setup does not change how a curve bends as input explodes.
Say an algorithm does 3n + 100 steps. For small n the hundred dominates. But as n reaches millions, the 3n swamps it, and the factor three does not change that it grows linearly. So we call it O(n).
This keeps comparisons honest and hardware-free. A constant might just come from one machine being faster. By ignoring it, Big-O captures the property that survives across computers: which algorithm pulls ahead as the problem gets large.
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 -
Ordered from cheapest to most expensive as input grows, the common classes run like this:
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. The jumps are brutal. At a thousand items, linear is a thousand steps while quadratic is a million. Anything exponential or factorial becomes hopeless 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 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?
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?
How do you spot accidental exponential blowup in recursive branching?
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 cheatsheet
- 30-second mental model01
- Growth classes (fastest -> slowest)02
- Deriving the answer03
- Data structure op costs (average / worst)04
- Sorting05
- Common per-task costs06
- Space complexity07
- Amortized08
- Picking a target from n09
- Common pitfalls10
- + 4 more inside
46 of 53 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.