Big-O notation describes the asymptotic growth of an algorithm's cost as input size increases — most often applied to worst-case running time or memory, expressed as O(n), O(n2), O(logn), etc.
Does doubling the data double the time? Or quadruple it? Or barely change it?
Showing a random 20 of 76 problems.
Example 1
hard
Time-space tradeoff: a precomputed lookup table can answer queries in O(1) instead of O(logn) each. When is this worth it?
Example 2
hard
You must check if any two of n numbers sum to a target T. A naive double loop is O(n2). Describe a more efficient approach and give its complexity.
Example 3
hard
What is the time complexity of inserting at the front of an array of size n?
Example 4
hard
Rank these time complexities from most to least efficient: O(n2), O(1), O(nlogn), O(n), O(2n).
Example 5
hard
Algorithm A takes 100 steps for an input of size 10 and 400 steps for size 20. Algorithm B takes 10 steps for size 10 and 20 steps for size 20. Which is more efficient and what might their time complexities be?Algorithm A: steps at n=10 vs n=20 (quadratic growth)
Example 6
easy
What is the Big-O of three nested loops each running n times?
Example 7
easy
Big-O describes the worst-case growth rate of a function as input size approaches what?
Example 8
challenge
Counting sort runs in O(n+k) where k is the value range. When does it beat comparison sorts' O(nlogn)?
Example 9
medium
Amortized analysis: appending to a dynamic array sometimes triggers a resize. What is the amortized cost per append?
Example 10
medium
What is the time complexity of bubble sort in the worst case?
Example 11
medium
An algorithm runs in T(n)=1000n ms and another in U(n)=n2 ms. Which is faster when n=10? When n=10000?T(n)=1000n is faster for n>1000; crossover with U(n)=n² is at n=1000
Example 12
medium
A function has runtime T(n)=5n2+20n+100. What is its tightest Big-O?
Example 13
medium
Merge sort runs in O(nlogn). Roughly how many operations does it perform on n=1,048,576=220 items?Merge sort O(n log n): at n=2²⁰ ≈ 1M items, only ~20 million operations
Example 14
hard
Rank from fastest to slowest growth for large n: O(n!), O(n3), O(logn), O(nlogn), O(n).
Example 15
medium
An algorithm halves the input each step until size 1, doing constant work per step. What is its complexity?Halving algorithm: steps = log₂ n
Example 16
easy
Does Big-O describe the upper bound or the exact running time?
Example 17
easy
An algorithm has nested loops, the outer over n items and the inner over the same n items. What is its time complexity?
Example 18
easy
Binary search on a sorted array of size n has what time complexity?
Example 19
hard
Algorithm A runs in TA(n)=100n, and algorithm B runs in TB(n)=n2. For what range of n is algorithm B actually faster?
Example 20
easy
A loop runs once per element of an array of size n. What is its Big-O time complexity?Single loop over n elements: O(n) — iterations match input size exactly