18:35 3.6 Dijkstra Algorithm - Single Source Shortest Path - Greedy Method Abdul Bari
4.6M views · 72.1K likes · 8 years ago
What Is Big O Notation?
Big O notation describes how an algorithm's time or space requirements grow as input size increases. O(1) is constant time (instant regardless of input), O(n) is linear (grows proportionally), O(n²) is quadratic (grows with the square). It's the standard way to discuss algorithm efficiency.
How Big O Notation Works
O(1): accessing array[5] — same speed whether the array has 10 or 10 million items. O(n): looping through every item. O(log n): binary search — halves the search space each step. O(n²): nested loops comparing every pair — 1,000 items = 1,000,000 operations.
Practical impact: O(n) algorithm on 1M items: 1 million operations (~1ms). O(n²) on 1M items: 1 trillion operations (~16 minutes). O(n log n) on 1M items: 20 million operations (~20ms). Big O tells you which algorithms will scale.
Why Developers Use Big O Notation
You don't need to analyze every function mathematically. But recognizing that nested loops are O(n²) and hash lookups are O(1) helps you write code that doesn't collapse under load.
Key Concepts
- O(1) — Constant — Same time regardless of input size — hash table lookup, array index access
- O(log n) — Logarithmic — Halves the problem each step — binary search, balanced tree operations
- O(n) — Linear — Proportional to input — single loop through data, linear search
- O(n log n) — Linearithmic — Efficient sorting — merge sort, quicksort average case
- O(n²) — Quadratic — Nested loops — bubble sort, comparing every pair, brute force matching
- O(2^n) — Exponential — Doubles each step — recursive Fibonacci, brute force combinatorics
Learn Big O Notation — Top Videos
18:35 
36:54 But what is quantum computing? (Grover's Algorithm) 3Blue1Brown
3.1M views · 84.5K likes · 10 months ago
48:57 Acing Google Coding Interview as an 18 year old High School Student William Lin (tmwilliamlin168)
2.9M views · 50.1K likes · 5 years ago
8:26 Namaste DSA 🚀 - Zero to Hero course for Data Structures & Algorithm Akshay Saini
2.5M views · 3.1K likes · 9 months ago
Big O Notation Educators
Gate Smashers
@gatesmashers
Data Science
Welcome to Gate Smashers, one of the fastest-growing EdTech communities with 2.6 M+ learners. 🎓 We provide complete lec...
2.6M Subs
2K Videos
13.8K Avg Views
1.58% Engagement
NeetCode
@neetcode
CS
Current NEET and ex-Google SWE, also I love teaching! N.E.E.T. = (Not in education, employment or training) Preparing ...
1.1M Subs
414 Videos
128.4K Avg Views
3.99% Engagement
NeuralNine
@neuralnine
Web Dev
NeuralNine is an educational brand focusing on programming, machine learning and computer science in general! Let's deve...
461K Subs
1K Videos
14.3K Avg Views
4.77% Engagement
Greg Hogg
@greghogg
Data Science
Today, Greg is driven by a single mission: to help engineers master the complex technical skills required to land roles ...
309K Subs
1.3K Videos
9.1K Avg Views
3.31% Engagement
Frequently Asked Questions
Does Big O matter for small inputs?
Not much. O(n²) on 100 items is 10,000 operations — fine. But code that works on 100 items may fail on 100,000. Think about your expected data size.
What Big O should I aim for?
O(n log n) or better for sorting/searching. O(1) for lookups (use hash maps). Avoid O(n²) when possible. Sometimes O(n²) is acceptable for small datasets.
Want a structured learning path?
Plan a Big O Notation Lesson →