Scribd
Upload
8 views1 page

Algorithm Time and Space Complexities

Uploaded by

Rahul dev shaha
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
8 views1 page

Algorithm Time and Space Complexities

Uploaded by

Rahul dev shaha
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

Algorithm Time and Space Complexities

Algorithm Space Complexity Time Complexity (Best / Worst)

Bubble Sort O(1) O(n^2) / O(n^2)

Selection Sort O(1) O(n^2) / O(n^2)

Insertion Sort O(1) O(n) / O(n^2)

Merge Sort O(n) O(n log n) / O(n log n)

Quick Sort O(log n) O(n log n) / O(n^2)

Heap Sort O(1) O(n log n) / O(n log n)

Counting Sort O(k) O(n + k) / O(n + k)

Radix Sort O(n + k) O(nk) / O(nk)

Bucket Sort O(n + k) O(n + k) / O(n^2)

Shell Sort O(1) O(n log n) / O(n^2)

Tim Sort O(n) O(n log n) / O(n log n)

Comb Sort O(1) O(n log n) / O(n^2)

Pigeonhole Sort O(n + r) O(n + r) / O(n + r)

Cycle Sort O(1) O(n^2) / O(n^2)

Bitonic Sort O(log^2 n) O(log^2 n) / O(log^2 n)

Linear Search O(1) O(n) / O(n)

Binary Search O(1) O(log n) / O(log n)

Jump Search O(1) O(√n) / O(√n)

Interpolation Search O(1) O(log log n) / O(n)

Exponential Search O(1) O(log n) / O(log n)

Fibonacci Search O(1) O(log n) / O(log n)

Ternary Search O(1) O(log n) / O(log n)

Sublist Search O(1) O(n*m) / O(n*m)

Hashing-based Search O(1) O(1) / O(n)

Depth-First Search (DFS) O(V) O(V + E) / O(V + E)

Breadth-First Search (BFS) O(V) O(V + E) / O(V + E)

You might also like