Scribd
Upload
3 views3 pages

Algorithm & Data Structure Complexity Reference

The document provides a Big-O complexity chart categorizing algorithms into excellent, good, fair, bad, and horrible based on their time complexities. It includes various searching algorithms like Depth First Search, Breadth First Search, and Binary Search, along with their respective time and space complexities. Additionally, it details heap data structures and their associated time complexities for operations like heapify, find max, and extract max.

Uploaded by

saijahnavi.pasumarthi2004
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
3 views3 pages

Algorithm & Data Structure Complexity Reference

The document provides a Big-O complexity chart categorizing algorithms into excellent, good, fair, bad, and horrible based on their time complexities. It includes various searching algorithms like Depth First Search, Breadth First Search, and Binary Search, along with their respective time and space complexities. Additionally, it details heap data structures and their associated time complexities for operations like heapify, find max, and extract max.

Uploaded by

saijahnavi.pasumarthi2004
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

Print to P

Big-O Complexity Chart

Excellent Good Fair Bad Horrible

O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ)

Elements →

🔄 Array Sorting Algorithms


🏗 Data Structures

🔍 Searching Algorithms

Algorithm Data Structure Time Complexity Space

Average Worst Worst

Depth First Search (DFS) Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V|)

Breadth First Search (BFS) Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V|)

Binary Search Sorted array of n elements O(log n) O(log n) O(1)

Linear (Brute Force) Array O(n) O(n) O(1)

Shortest path by Dijkstra (Min-heap) Graph with |V| vertices and |E| edges O((|V| + |E|) log |V|) O((|V| + |E|) log |V|) O(|V|)

Shortest path by Dijkstra (Unsorted array) Graph with |V| vertices and |E| edges O(|V|²) O(|V|²) O(|V|)

Shortest path by Bellman-Ford Graph with |V| vertices and |E| edges O(|V||E|) O(|V||E|) O(|V|)
🏔 Heap Data Structures

Heaps Time Complexity

Heapify Find Max Extract Max Increase Key Insert Delete Merge

Linked List (sorted) - O(1) O(1) O(n) O(n) O(1) O(m+n)

Linked List (unsorted) - O(n) O(n) O(1) O(1) O(1) O(1)

Binary Heap O(n) O(1) O(log n) O(log n) O(log n) O(log n) O(m+n)

Binomial Heap - O(log n)

You might also like