learningto/pass

Big-O Notation

BeginnerConcepts

Big-O is the language of algorithm analysis. Every Google solution you present must come with a complexity analysis. This is non-negotiable. Understand how to derive it, not just memorize it.

AVG TIME
N/A
SPACE
N/A
BEST
N/A
WORST
N/A

Key Concepts

  • 1Drop constants and lower-order terms: O(2n + 5) = O(n)
  • 2Nested loops multiply: two nested O(n) loops = O(n^2)
  • 3Recursive calls: T(n) = aT(n/b) + f(n) - Master Theorem
  • 4Space complexity counts both explicit storage AND call stack depth
  • 5Amortized analysis: dynamic array append is O(1) amortized despite O(n) resizes

In Python

Concept to Code- 3 structures for this topic
declare
nums = [1, 2, 3]
common ops
nums.append(x)
O(1)
nums.pop()
O(1)
nums[i]
O(1)
nums.insert(i, x)
O(n)
x in nums
O(n)
nums.sort()
O(n log n)
len(nums)
O(1)
say in interview
"I'll use an array to store the elements"
Python lists ARE dynamic arrays (like ArrayList in Java), NOT linked lists. Access by index is O(1).

Math You Need For This

A complexity cheat sheet: plot all classes on the same graph. See how quickly 2ⁿ and n! become vertical while O(n log n) stays nearly flat in comparison.

Required concepts
Key math ideas
1 / 6

Constant time - O(1)

No matter how large the input is, this operation always takes the same amount of time. The size of n simply does not matter.

Visual: A perfectly flat horizontal line on a graph. The line never rises no matter how far right you go.

Think of it this way: Looking up a word in a dictionary if you already know the exact page number. It does not matter how thick the dictionary is.

For algorithms: Accessing array[3] is O(1) because the computer calculates the memory address directly: start + 3 * item_size. One calculation, done.

Interactive 3D Visualization

Array
Access: O(1)Search: O(n)Space: O(n)
Drag to orbit - Scroll to zoom

Python Implementation

example.py
Loading...
Now try it yourself
1 challenge with test cases and AI feedback
Practice Now

Complexity Analysis

1481216n²nlog n1n (input size)
COMMON OPERATIONS
Array
Access:O(1)
Search:O(n)
Insert end:O(1)*
Insert mid:O(n)
Hash Map
Get/Set:O(1)*
Delete:O(1)*
Search value:O(n)
Iterate:O(n)
Linked List
Access:O(n)
Search:O(n)
Insert head:O(1)
Delete known:O(1)
Binary Search
Search:O(log n)
Insert:O(log n)
Balanced BST
Search:O(log n)
Insert:O(log n)
Delete:O(log n)
Heap
Peek min/max:O(1)
Push:O(log n)
Pop:O(log n)
Heapify:O(n)
Graph (BFS/DFS)
Traversal:O(V+E)
Dijkstra (heap):O((V+E) log V)
Merge / Quick Sort
Sort:O(n log n)
Space (merge):O(n)
Space (quick):O(log n)

* amortized average case

READY TO TEST YOURSELF?

Put Big-O Notation into practice

The best way to lock in what you've learned is to write code. Solve real interview-style problems right now.

Big-O Notation
Next: System Design Basics