Big-O چیٹ شیٹ
قابل تلاش، قابل پرنٹ Big-O حوالہ: ارے، ہیش ٹیبلز، ٹریز، ہیپس، گرافس، ترتیب اور تلاش کی ٹائم اور اسپیس کمپلیکسٹی۔ مفت۔
Complexity classes
12O(1): constant
Same cost regardless of input size
O(log n): logarithmic
Halves the problem each step
O(n): linear
Touches every element once
O(n log n): linearithmic
Best possible comparison sort
O(n²): quadratic
Every pair: nested loops over input
O(n³): cubic
Triple nesting, e.g. naive matrix multiply
O(2^n): exponential
Doubles per element: all subsets
O(n!): factorial
All orderings: brute-force permutations
n = 10^6: O(n log n) ≈ 2×10^7 ops
Fine: well under a second
n = 10^6: O(n²) = 10^12 ops
Too slow: think minutes to hours
Rule: drop constants and lower terms
O(3n² + 5n) is just O(n²)
Amortized O(1)
Occasionally slow, cheap on average
Arrays & dynamic arrays
11Access by index: O(1)
Direct address arithmetic
Search (unsorted): O(n)
Must scan every element
Search (sorted): O(log n)
Binary search on sorted data
Append (dynamic): O(1) amortized
Occasional resize copies all
Insert at front/middle: O(n)
Shifts all later elements
Delete at end: O(1)
No shifting required
Delete at front/middle: O(n)
Shifts elements to close the gap
Resize (grow ×2): O(n)
Copy into a bigger buffer
Slice/copy: O(k)
Proportional to slice length
Space: O(n)
May hold up to 2× capacity slack
Cache-friendly: contiguous memory
Real-world edge over linked lists
Linked lists
10Access by index: O(n)
Must walk from the head
Search: O(n)
Linear scan, no shortcuts
Insert/delete at head: O(1)
Repoint the head pointer
Insert/delete at tail: O(1) with tail ptr
O(n) without one (singly)
Insert after known node: O(1)
The big win over arrays
Delete known node (doubly): O(1)
Prev pointer makes unlink cheap
Delete known node (singly): O(n)
Must find the predecessor
Reverse: O(n) time, O(1) space
Classic pointer-flip interview task
Detect cycle: O(n), O(1) space
Floyd's tortoise and hare
Space: O(n) plus pointer overhead
1–2 pointers per node
Stacks & queues
10Stack push/pop/peek: O(1)
LIFO: last in, first out
Stack search: O(n)
No random access
Queue enqueue/dequeue: O(1)
FIFO: first in, first out
Deque push/pop both ends: O(1)
Double-ended queue
Queue via 2 stacks: O(1) amortized
Classic interview construction
Min-stack: O(1) getMin
Track min alongside each push
Monotonic stack: O(n) total
Next greater element problems
Stack use: DFS, undo, call stack
Recursion is an implicit stack
Queue use: BFS, schedulers, buffers
Level-order processing
Space: O(n)
One slot per stored element
Hash tables
11Insert: O(1) avg, O(n) worst
Worst = all keys collide
Lookup: O(1) avg, O(n) worst
Hash, then probe the bucket
Delete: O(1) avg, O(n) worst
Same story as lookup
Resize/rehash: O(n)
Triggered past the load factor
Load factor ~0.7
Typical resize threshold
Chaining
Collisions become linked lists
Open addressing
Probe for the next free slot
Ordered iteration: not provided
Use a tree map if order matters
Hash set membership: O(1) avg
The go-to de-dupe structure
Space: O(n)
Plus empty buckets overhead
Pattern: trade O(n) space for O(1) lookups
Two-sum in one pass
Binary search trees & balanced trees
12BST search/insert/delete: O(h)
h = tree height
BST average: O(log n)
Random inserts stay bushy
BST worst: O(n)
Sorted inserts make a chain
AVL all ops: O(log n) guaranteed
Strict balance, fast lookups
Red-black all ops: O(log n)
Looser balance, faster writes
B-tree all ops: O(log n)
Wide nodes: databases, disks
In-order traversal: O(n)
Visits keys in sorted order
Min/max: O(log n) balanced
Walk far left / far right
Successor/predecessor: O(log n)
Ordered neighbors of a key
Range query: O(log n + k)
k = number of results
Trie lookup: O(L)
L = key length, not item count
Space: O(n)
2–3 pointers per node
Heaps
10Peek min/max: O(1)
Root holds the extreme
Insert: O(log n)
Bubble up to restore order
Extract min/max: O(log n)
Pop root, sift down
Build heap from array: O(n)
Heapify beats n inserts
Search arbitrary key: O(n)
Heaps are not for lookups
Decrease-key: O(log n)
Core of Dijkstra's algorithm
Top-k of n items: O(n log k)
Keep a size-k heap
Two heaps: O(log n) per insert
Running median pattern
Stored as an array
Children at 2i+1, 2i+2
Space: O(n)
No pointers needed
Graphs
12Adjacency list space: O(V + E)
Best for sparse graphs
Adjacency matrix space: O(V²)
Best for dense graphs
Edge check: list O(deg), matrix O(1)
The core trade-off
Iterate neighbors: list O(deg), matrix O(V)
Lists win for traversal
BFS / DFS: O(V + E)
With an adjacency list
Topological sort: O(V + E)
DAG ordering (Kahn / DFS)
Dijkstra: O((V + E) log V)
Binary heap, no negative edges
Bellman-Ford: O(V·E)
Handles negative edges
Floyd-Warshall: O(V³)
All-pairs shortest paths
Prim / Kruskal MST: O(E log V)
Minimum spanning tree
Union-Find: O(α(n)) ≈ O(1)
With rank + path compression
A*: O(E) best case
Heuristic-guided Dijkstra
Sorting algorithms
13Bubble sort: O(n²), best O(n)
O(1) space; only teaching value
Insertion sort: O(n²), best O(n)
O(1) space; great when nearly sorted
Selection sort: O(n²) always
O(1) space; fewest swaps
Merge sort: O(n log n) always
O(n) space; stable; predictable
Quick sort: avg O(n log n), worst O(n²)
O(log n) space; fastest in practice
Heap sort: O(n log n) always
O(1) space; not stable
Tim sort: O(n log n), best O(n)
Python/Java built-in; stable
Counting sort: O(n + k)
k = value range; not comparison
Radix sort: O(d·(n + k))
d = digits; ints and strings
Bucket sort: avg O(n + k), worst O(n²)
Uniformly distributed input
Shell sort: ~O(n^1.3)
Gap-based insertion sort
Comparison-sort lower bound: Ω(n log n)
Cannot do better by comparing
Stable: merge, insertion, tim, counting
Equal keys keep their order
Searching algorithms
11Linear search: O(n)
Only option for unsorted data
Binary search: O(log n)
Sorted arrays only
Binary search space: O(1) iterative
O(log n) if recursive
Hash lookup: O(1) avg
Fastest membership test
BST search: O(log n) balanced
Also gives sorted neighbors
Trie prefix search: O(L)
Autocomplete workhorse
BFS shortest path (unweighted): O(V + E)
First hit is the shortest
lower_bound / bisect: O(log n)
First element >= target
Quickselect (k-th element): avg O(n)
Worst O(n²); no full sort
Ternary search: O(log n)
Peak of a unimodal function
Interpolation search: avg O(log log n)
Uniform sorted data only
Common patterns
12Two pointers: O(n)
Pair sums in a sorted array
Sliding window: O(n)
Best subarray of size/condition k
Fast & slow pointers: O(n)
Cycle detection, list middle
Prefix sums: O(n) build, O(1) query
Range-sum questions
Binary search on answer: O(n log range)
"Min capacity to ship in D days"
Monotonic stack: O(n)
Next greater / histogram area
Backtracking: O(2^n) or O(n!)
Subsets / permutations search
Memoized DP: states × transition cost
Kills exponential recursion
Greedy: usually O(n log n)
Sort, then one linear pass
Divide & conquer: T(n) = 2T(n/2) + O(n)
Master theorem: O(n log n)
Bit manipulation: O(1) per op
Sets of <=64 items in an int
Meet in the middle: O(2^(n/2))
Halves an exponential search
Space complexity notes
11In-place: O(1) extra space
Quick sort, heap sort, reversal
Recursion costs stack space
Depth d means O(d) memory
DFS space: O(h) / O(V) worst
h = depth of recursion
BFS space: O(w)
w = widest level (can be n/2)
Merge sort: O(n) auxiliary
The price of stability
Memoization: O(#states)
Time saved, memory spent
DP table row trick: O(n²) → O(n)
Keep only the previous row
Hash-based de-dupe: O(n) space
vs O(1) sort-first approach
Tail recursion: O(1) if optimized
Not guaranteed in every language
Streaming: O(1) or O(k) space
One pass, constant memory
Always state time AND space
Interviews expect both
کوئی اندراج “:q” سے میل نہیں کھاتا۔
Big-O چیٹ شیٹ کے بارے میں
یہ Big-O چیٹ شیٹ الگورتھمک پیچیدگی کو ایک قابل تلاش صفحے پر رکھتی ہے: خود پیچیدگی کی کلاسز، پھر ارے اور ڈائنامک ارے، لنکڈ لسٹس، سٹیکس اور کیوز، ہیش ٹیبلز، بائنری سرچ ٹریز اور متوازن ٹریز، ہیپس، گرافس، ترتیب دینے کے الگورتھمز، تلاش کے الگورتھمز، عام پیٹرنز، اور اسپیس کمپلیکسٹی کے نوٹس کے وقت اور اسپیس کے اخراجات۔
یہ ڈیٹا سٹرکچر کے انتخاب اور انٹرویو کی تیاری، دونوں کے لیے حوالہ ہے: ہیش ٹیبل لوک اپ کا اوسط اور بدترین کیس، متوازن ٹری سادہ BST سے بہتر کیوں ہے، کون سی ترتیب مستحکم ہے اور کون سی ان پلیس، اور ٹو پوائنٹر، سلائیڈنگ ونڈو اور میموائزیشن پیٹرنز کی لاگت کیا ہے۔
شیٹ مفت اور کلائنٹ سائیڈ ہے: سرچ باکس سے قطاروں کو لائیو فلٹر کریں، چپکے رہنے والی فہرست مضامین سے حصوں کے درمیان کودیں، ایک کلک سے کوئی بھی اندراج کاپی کریں اور میز کے حوالے کے طور پر صفحہ پرنٹ کریں۔
Big-O چیٹ شیٹ استعمال کرنے کا طریقہ
- شیٹ کھولیں اور O(1)، O(log n)، O(n)، O(n log n) اور O(n²) کو ذہن نشین کرنے کے لیے Complexity classes سے شروع کریں۔
- hash table، quicksort یا BFS جیسا کوئی ڈیٹا سٹرکچر یا الگورتھم تلاش کریں تاکہ ہر قطار لائیو فلٹر ہو جائے۔
- جب آپ فہرست، میپ اور ٹری میں سے انتخاب کر رہے ہوں تو ڈیٹا سٹرکچر کے حصوں کا موازنہ کریں۔
- اندراج کو اپنی کلپ بورڈ پر کاپی کرنے کے لیے اس پر یا اس کے کاپی آئیکن پر کلک کریں۔
- آف لائن پیچیدگی کے حوالے کے لیے شیٹ پرنٹ کریں۔
اکثر پوچھے جانے والے سوالات
بارہ حصے: پیچیدگی کی کلاسز، ارے اور ڈائنامک ارے، لنکڈ لسٹس، سٹیکس اور کیوز، ہیش ٹیبلز، بائنری سرچ اور متوازن ٹریز، ہیپس، گرافس، ترتیب دینے کے الگورتھمز، تلاش کے الگورتھمز، عام پیٹرنز، اور اسپیس کمپلیکسٹی کے نوٹس۔
جی ہاں۔ جہاں وہ مختلف ہوں (ہیش ٹیبل لوک اپس، quicksort، غیر متوازن BST) وہاں قطار دونوں بتاتی ہے، تاکہ آپ دیکھ سکیں کہ ڈیٹا مخالفانہ ہونے پر لاگت کیا ہے۔
یہ بالکل اسی کے لیے بنی ہے: ترتیب اور تلاش کے حصے اور عام پیٹرنز کا حصہ ان پیچیدگیوں کا احاطہ کرتے ہیں جنہیں انٹرویو لینے والے آپ سے بلند آواز میں بتانے کو کہتے ہیں۔
جی ہاں۔ اسپیس کی لاگتیں وقت کی لاگتوں کے ساتھ آتی ہیں، اور آخری حصہ ریکرژن اسٹیک کی گہرائی، ان پلیس بمقابلہ اضافی اسپیس اور عام سمجھوتوں کا احاطہ کرتا ہے۔
جی ہاں، مکمل طور پر مفت: قابل تلاش، قابل پرنٹ اور بغیر سائن اپ کے آپ کے براؤزر میں رینڈر ہوتا ہے۔
مقبول تلاشیں
big o چیٹ شیٹ
ٹائم کمپلیکسٹی چارٹ
ڈیٹا سٹرکچر کمپلیکسٹی
سورٹنگ الگورتھم کمپلیکسٹی
big o نوٹیشن جدول
اسپیس کمپلیکسٹی چارٹ
الگورتھم کمپلیکسٹی حوالہ
مدد چاہیے؟
اس ٹول میں کوئی مسئلہ ملا؟ ہماری ٹیم کو بتائیں۔