Big-O Notation/Practice/Complexity Analysis Practice
Big-O Complexity Analysis - Practice Explained
Read each function and ask three questions: does the loop shrink the input (halving → log n), does work nest (nested full loops → multiply), or is the work constant per element (single pass → n)? Then verify by counting operations as inputs grow.
Why it works
Complexity classes are about shape, not speed: an O(n) loop and an O(n²) loop may both be fast at n = 10, and both crawl at n = 10 billion. Counting operations at increasing input sizes shows which curve you are on - and which optimizations actually matter.
The problem
Implement three functions with specific complexity targets, then verify by counting operations. Goal: understand why complexity classes matter in practice.
Hints
- O(n log n): sort the array, then scan for adjacent equal elements.
- O(n): use a set to track seen numbers. If num already in set, it is a duplicate.
- O(1) space trick: for each num, negate nums[abs(num)-1]. If it's already negative, it's a duplicate.
Test cases
| Input | Expected |
|---|---|
find_duplicates_linear([4,3,2,7,8,2,3,1]) | [2,3] |
find_duplicates_constant_space([4,3,2,7,8,2,3,1]) | [2,3] |
Reference starter code
# Part 1: Implement a function that is O(n log n)
def find_duplicates_n_log_n(nums):
# Sort first, then scan for adjacent duplicates
pass
# Part 2: Improve it to O(n) using a hash set
def find_duplicates_linear(nums):
pass
# Part 3: O(n) time and O(1) space
# if nums contains values in range [1, n]
def find_duplicates_constant_space(nums):
# Use the array itself as a hash map by negating visited indices
pass
test = [4, 3, 2, 7, 8, 2, 3, 1]
print(find_duplicates_n_log_n(test))
print(find_duplicates_linear(test))
print(find_duplicates_constant_space(test))
Try it yourself
Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.