CodingPrepGuide.com • Official 1-Page Reference

Big-O Complexity & Data Structures Printable Cheat Sheet

Time & Space Complexity for All Core Data Structures & Sorting Algorithms

⚡

⚡ Quick-Decision Recognition Triggers

› O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

› 10^7 operations ≈ 1 second of CPU execution in competitive coding / interview sandbox

› For N = 10^5: O(n log n) or O(n) required (O(n²) will Time Out)

› For N = 20: O(2ⁿ) Backtracking is acceptable

› For N = 500: O(n³) or O(n²) DP is acceptable

Data Structure Operation Complexities 1-Page Cheatsheet

Access: O(1) | Search: O(N) | Insert/Delete: O(N) | Append: O(1) amortized

When to use: Contiguous memory

Fast indexed reads. Expensive middle insertions.

Access: O(N) | Search: O(N) | Insert at Head: O(1) | Delete Node: O(1) with pointer

When to use: Node pointers

Fast head prepend; slow random access.

Search: O(1) avg, O(N) worst | Insert: O(1) avg | Delete: O(1) avg

When to use: Hash buckets

Collision resolution via chaining or open addressing.

Search: O(log N) | Insert: O(log N) | Delete: O(log N)

When to use: AVL / Red-Black

Maintains sorted order. Unbalanced degrades to O(N).

Find Min/Max: O(1) | Insert: O(log N) | Extract: O(log N) | Heapify: O(N)

When to use: Complete binary tree

Used for Top K, Dijkstra, scheduling.

Best: O(N log N) | Avg: O(N log N) | Worst: O(N²) | Space: O(log N)

When to use: Divide & conquer pivot

In-place, not stable. Worst case occurs with bad pivot selection.

Best: O(N log N) | Avg: O(N log N) | Worst: O(N log N) | Space: O(N)

When to use: Divide & merge halves

Stable sort. Guaranteed O(N log N) time regardless of input.

Best: O(N log N) | Avg: O(N log N) | Worst: O(N log N) | Space: O(1)

When to use: Binary heap in-place

Guaranteed O(N log N) with zero auxiliary memory.

CodingPrepGuide.com • Free Coding Interview Preparation • No Sign-Up Required