Comprehensive Big O Notation and Data Structure Algorithms Review

What is Big O Notation?

It describes how runtime or space grows as input size increases.

What is the Big O of a loop that runs n times?

O(n)

What is the Big O of nested loops each running n times?

O(n²)

What is the Big O of binary search?

O(log n)

What are quicksort's average and worst case complexities?

Average: O(n log n), Worst: O(n²)

What is merge sort's space complexity?

O(n)

Order from best to worst efficiency: O(1), O(log n), O(n), O(n log n), O(n²), O(2^n), O(n!)

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)

Access by index in an array

O(1)

Insert/remove from middle of an array

O(n)

Access nth element in a linked list

O(n)

Insert/delete at head of linked list

O(1)

Advantage of linked list over array

Dynamic size and easy insertion/deletion

Stack push/pop/peek time complexity

O(1)

Queue enqueue/dequeue time complexity

O(1)

Average insert/delete/lookup in hash table

O(1)

Worst case hash table operations

O(n)

What is a hash collision?

When two keys hash to the same index

Search in a balanced BST

O(log n)

Search in an unbalanced BST

O(n)

Traverse a binary tree

O(n)

DFS uses what data structure?

Stack or recursion

BFS uses what data structure?

Queue

Insert into a binary heap

O(log n)

Extract-min or extract-max from a heap

O(log n)

Find-min in a min-heap

O(1)

BFS or DFS time complexity on graph

O(V + E)

Dijkstra's Algorithm complexity

O((V + E) log V)

What is the "Two Pointers" pattern?

Using two indices to optimize array/string traversal

What is the "Sliding Window" pattern?

Maintaining a window for subarray/subsequence analysis

What is "Divide and Conquer"?

Divide problem into subproblems, solve recursively, combine results

What is "Dynamic Programming"?

Storing subproblem results to avoid recomputation

Binary Search time and space complexity

Time: O(log n), Space: O(1)

Merge Sort time and space complexity

Time: O(n log n), Space: O(n)

Quick Sort average and worst case

Avg O(n log n), Worst O(n²)

Iterative BFS uses what data structure?

Queue

Iterative DFS uses what data structure?

Stack

Graph traversal using adjacency list complexity

O(V + E)

How to detect cycle in linked list?

Use two pointers (fast and slow); if they meet, a cycle exists.