Scribd
Upload
5 views3 pages

Time Complexity of Popular Algorithms

The document provides a comprehensive overview of the time and space complexities for various algorithms, including search, sorting, graph, and dynamic programming algorithms. It details best, average, and worst-case scenarios for each algorithm, along with additional notes on their characteristics. Key algorithms discussed include Linear Search, Binary Search, Quick Sort, Merge Sort, and Dijkstra’s Algorithm, among others.

Uploaded by

Kartikay Pant
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views3 pages

Time Complexity of Popular Algorithms

The document provides a comprehensive overview of the time and space complexities for various algorithms, including search, sorting, graph, and dynamic programming algorithms. It details best, average, and worst-case scenarios for each algorithm, along with additional notes on their characteristics. Key algorithms discussed include Linear Search, Binary Search, Quick Sort, Merge Sort, and Dijkstra’s Algorithm, among others.

Uploaded by

Kartikay Pant
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

TIME COMPLEXITY

Algorithm Best Case Average Case Worst Case Space Complexity

Linear Search
O(1) O(n) O(n) O(1)
(unsorted)
Linear Search (sorted) O(1) O(n) O(n) O(1)

Binary Search O(1) iterative, O(log


O(1) O(log n) O(log n)
(Iterative/Recursive) n) recursive

Tower of Hanoi - - O(2ⁿ) O(n)


Fibonacci (Recursive) - - O(2ⁿ) O(n)
O(n) or O(1) (with
Fibonacci (DP) - - O(n)
space optimization)

Algorithm Best Average Worst Space Stable In-place


Bubble Sort O(n) O(n²) O(n²) O(1) Yes Yes

Insertion Sort O(n) O(n²) O(n²) O(1) Yes Yes

Selection Sort O(n²) O(n²) O(n²) O(1) No Yes

Quick Sort O(n log n) O(n log n) O(n²) O(log n) No Yes

Randomized Quick O(n log n) O(n²)


- O(log n) No Yes
Sort expected worst

Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes No
Heap Sort O(n log n) O(n log n) O(n log n) O(1) No Yes
Counting Sort O(n + k) O(n + k) O(n + k) O(k) Yes No

Space
Algorithm Time Complexity Notes
Complexity

BFS uses queue, DFS uses


BFS / DFS O(V + E) O(V)
stack/recursion
Topological Sort O(V + E) O(V) DAG only

Cycle Detection (DFS or Union-


O(V + E) O(V) DFS or Disjoint Sets
Find)
Strongly Connected
O(V + E) O(V) 2-pass DFS
Components (Kosaraju)

Kruskal’s Algorithm O(E log E) O(V) Uses Disjoint Set

Prim’s Algorithm O(E + log V) O(V) Min-heap + Adjacency List

Dijkstra’s Algorithm O((V + E) log V) O(V) Greedy, for +ve weights


Works with negative
Bellman-Ford O(VE) O(V)
weights
Floyd-Warshall O(V³) O(V²) All-pairs shortest path

Problem Time Complexity Space Notes

Activity Selection O(n log n) O(1) Sort by finish time

Job Sequencing O(n²) or O(n log n) O(n) Greedy slot filling

Fractional Knapsack O(n log n) O(1) Sort by value/weight

Huffman Coding O(n log n) O(n) Min heap used

Problem Time Space Notes


Fibonacci (DP) O(n) O(n) or O(1) Tabulation
0/1 Knapsack O(nW) O(nW) W = capacity
LCS O(mn) O(mn) String matching

Matrix Chain Multiplication O(n³) O(n²) Min multiplication cost

Method Time Complexity (Avg) Worst Case Space

Hashing (Chaining) O(1) O(n) O(n)

Hashing (Open
O(1) O(n) O(n)
Addressing)
Algorithm Time Complexity Space Notes

Naive O(nm) O(1) Simple comparison

Rabin-Karp O(n + m), Avg O(n + m) Uses hashing

KMP O(n + m) O(m) Builds prefix table

You might also like