Scribd
Upload
16 views2 pages

Algorithm

The document provides a comparison of various sorting algorithms and data structures, detailing their time complexities for best, average, and worst cases, as well as space complexities and notes on their use cases. Algorithms like Merge Sort and Quick Sort are highlighted for their efficiency, while Bubble Sort and Selection Sort are noted as less efficient. Additionally, it includes data structure access times for operations such as search, insert, and delete, emphasizing the characteristics of each structure.

Uploaded by

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

Algorithm

The document provides a comparison of various sorting algorithms and data structures, detailing their time complexities for best, average, and worst cases, as well as space complexities and notes on their use cases. Algorithms like Merge Sort and Quick Sort are highlighted for their efficiency, while Bubble Sort and Selection Sort are noted as less efficient. Additionally, it includes data structure access times for operations such as search, insert, and delete, emphasizing the characteristics of each structure.

Uploaded by

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

Average Worst

Algorithm Best Case Space Notes / Use Case


Case Case
Bubble Sort O(n) O(n²) O(n²) O(1) Simple, not efficient
Insertion Good for small/near-
O(n) O(n²) O(n²) O(1)
Sort sorted lists
Selection
O(n²) O(n²) O(n²) O(1) Always scans whole list
Sort
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Divide & conquer, stable
Quick Sort O(n log n) O(n log n) O(n²) O(log n) Fast in practice, unstable
Heap Sort O(n log n) O(n log n) O(n log n) O(1) Not stable, uses heap
Counting For small range integers
O(n+k) O(n+k) O(n+k) O(k)
Sort only
k = # of digits, non-
Radix Sort O(nk) O(nk) O(nk) O(n+k)
comparative
Binary
O(1) O(log n) O(log n) O(1) Sorted array required
Search
Linear
O(1) O(n) O(n) O(1) For small/unsorted arrays
Search
DFS (Graph) O(V+E) O(V+E) O(V+E) O(V) Recursive/stack-based
BFS (Graph) O(V+E) O(V+E) O(V+E) O(V) Uses queue
Dijkstra’s O(V²) / O(E + log V)
Same Same O(V) For shortest path
Algo with min-heap
Kruskal’s For MST (Minimum
O(E log E) O(E log E) O(E log E) O(E+V)
Algo Spanning Tree)
O(E + log O(E + log
Prim’s Algo O(E + log V) O(V) Another MST approach
V) V)
Data Structure Access Search Insert Delete Notes
Array O(1) O(n) O(n) O(n) Fixed size
Linked List O(n) O(n) O(1) O(1) Dynamic size
Stack O(n) O(n) O(1) O(1) LIFO
Queue O(n) O(n) O(1) O(1) FIFO
Hash Table O(1) O(1) O(1) O(1) Collisions can degrade to O(n)
Binary Tree O(log n) O(log n) O(log n) O(log n) Balanced tree assumed
BST (Unbalanced) O(n) O(n) O(n) O(n) Worst when unbalanced
AVL Tree O(log n) O(log n) O(log n) O(log n) Self-balancing BST
Heap O(n) O(n) O(log n) O(log n) Used in heap sort, priority queue
L = length of word, used for
Trie O(L) O(L) O(L) O(L)
dictionaries

You might also like