Scribd
Upload
5 views8 pages

Algorithms

The document provides a comprehensive overview of time and space complexities for various data structures and algorithms, including arrays, strings, stacks, queues, linked lists, trees, graphs, and maps. It details worst, average, and best case scenarios for operations such as accessing, updating, inserting, deleting, and searching elements. Additionally, it includes algorithm complexities for sorting and searching techniques, highlighting their performance metrics.

Uploaded by

puvishavb29
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 views8 pages

Algorithms

The document provides a comprehensive overview of time and space complexities for various data structures and algorithms, including arrays, strings, stacks, queues, linked lists, trees, graphs, and maps. It details worst, average, and best case scenarios for operations such as accessing, updating, inserting, deleting, and searching elements. Additionally, it includes algorithm complexities for sorting and searching techniques, highlighting their performance metrics.

Uploaded by

puvishavb29
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

Time complexity:

Worst Case Scenario Average Case Best Case Scenario


Scenario

Accessing an O(1) O(1) O(1)


element

Updating an O(1) O(1) O(1)


element

Deleting an O(n) O(n) O(1)


element

Inserting an O(n) O(n) O(1)


element

Searching for O(n) O(n) O(1)


an element

Arrays Algorithm complexity:

Time Complexity Space


Complexity
(Space-Time complexity) Worst Case Average Case Best Case

Quicksort O(n2) O(n log(n)) O(n log(n)) O(log(n))

Mergesort O(n log(n)) O(n log(n)) O(n log(n)) O(n)

Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)

Bubble Sort O(n2) O(n2) O(n) O(1)

Insertion Sort O(n2) O(n2) O(n) O(1)

Selection Sort O(n2) O(n2) O(n2) O(1)

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

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


Time complexity:
Worst Case Average Case Best Case Scenario
Scenario Scenario

Accessing O(1) O(1) O(1)

Deleting O(n) O(n) O(1)

Inserting O(n) O(n) O(1)

Searching O(n * m) O(n) O(1)


(n = string length
m = pattern length)

Slicing O(n) O(n) O(n)


(n = string length)

Concatenating O(n + m) O(n + m) O(n)


(n, m = string lengths)

Comparison O(n) O(n) O(n)

Strings
(n = shorter string length)

Inserting (Trie) O(m) O(m) O(1)


(m = key length)
(Space-time complexity)
Searching (Trie) O(m) O(m) O(1)
(m = key length)

Algorithm complexity:
Time Complexity Space
Complexity
Worst Case Average Best Case
Case

Radix sort O(n * m) O(n * m) O(n * m) O(n + m)


(m = longest string length)

Naive string search O(m*(n-m+1)) O(n * m) O(n) O(1)


(m = size of pattern)

Knuth-Morris-Pratt search O(m + n) O(n) O(n) O(m)

Boyer-Moore string search O(n * m) O(n) O(n/m) O(m)

Rubin-Karp Algorithm O(m*(n-m+1)) O(n + m) O(m) O(m)


Time complexity:

Worst Case Average Case Best Case Scenario


Scenario Scenario

Delete (Stack) O(1) O(1) O(1)

Insert (Stack) O(1) O(1) O(1)

Search (Stack) O(n) O(n) O(1)

Peek/Top (Stack) O(1) O(1) O(1)

Stacks & Delete (Queue) O(1) O(1) O(1)

Queues Insert (Queue) O(1) O(1) O(1)

(Space-time complexity) Search (Queue) O(n) O(n) O(1)

Algorithm Complexity:

Time Complexity Space


Complexity

Worst Case Average Case Best Case

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

Stack: LIFO (Last In First Out)

Queue: FIFO (First In First Out)


Time complexity:

Worst Case Scenario Average Case Scenario Best Case Scenario

Accessing O(n) O(n) O(1)

Deleting O(1) O(1) O(1)


(after search)

Inserting O(1) O(1) O(1)


(after search)

Searching O(n) O(n) O(1)

Traversing O(n) O(n) O(n)

Linked
Access (Skip List) O(n) O(log n) O(log n)

Delete (Skip List) O(n) O(log n) O(log n)

Lists Insert (Skip List)

Search (Skip List)


O(n)

O(n)
O(log n)

O(log n)
O(log n)

O(log n)
(Space-time complexity)

Algorithm Complexity:

Time Complexity Space Complexity

Worst Case Average Case Best Case

Mergesort O(n log n) O(n log n) O(n log n) O(n)

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

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

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

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


Time complexity:

Worst Case Average Case Best Case


Scenario Scenario Scenario

Binary Search Delete O(n) O(log n) O(log n)


Tree,
Cartesian Tree,
KD Tree Insert O(n) O(log n) O(log n)

Search O(n) O(log n) O(log n)

B-Tree, Delete O(log n) O(log n) O(log n)


Red-Black Tree,
Splay Tree,
AVL Tree Insert O(log n) O(log n) O(log n)

Search O(log n) O(log n) O(log n)

Trees Traversal O(n) O(n) O(n)

(Space-time complexity)

Algorithm Complexity:

Time Complexity Space


Complexity
Worst Case Average Best Case
Case

Depth-First Search O(n) O(n) O(n) O(n)


(In-order, pre-order, and
post-order traversal)

Breadth-First Search O(n) O(n) O(n) O(n)


(Level-order traversal)

Tree Sort O(n2) O(n log n) O(n log n) O(n)

Splaysort O(n log n) O(n log n) O(n) O(n)

Cartesian Tree Sort O(n log n) O(n log n) O(n) O(n)


Time Complexity:

Worst Case Average Case Best Case


Scenario Scenario Scenario

Insert Vertex Adjacency List O(1) O(1) O(1)

Adjacency Matrix O(V2) O(V2) O(V2)

Incidence Matrix O(V*E) O(V*E) O(V*E)

Remove Vertex Adjacency List O(E) O(E) O(E)

Adjacency Matrix O(V2) O(V2) O(V2)

Incidence Matrix O(V*E) O(V*E) O(V*E)

Insert Edge Adjacency List O(1) O(1) O(1)

Adjacency Matrix O(1) O(1) O(1)

Incidence Matrix O(V*E) O(V*E) O(V*E)

Graphs
Remove Edge Adjacency List O(V) O(V) O(V)

Adjacency Matrix O(1) O(1) O(1)

Incidence Matrix O(V*E) O(V*E) O(V*E)


(Space-time complexity)
Check if Adjacency List O(V) O(V) O(V)
Vertices
Adjacent Adjacency Matrix O(1) O(1) O(1)

Incidence Matrix O(E) O(E) O(E)

Algorithm Complexity:

Time Complexity Space Complexity

Worst Case Average Best Case


Case

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

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

A* Search O(E) O(E) O(E) O(V)

Dijkstra’s algorithm O(V2) O(E * log(V)) O(E * log(V)) O(V)

Floyd–Warshall O(V3) O(V3) O(V3) O(V2)


Time complexity:

Worst Case Average Case Best Case Scenario


Scenario Scenario

Updating an element O(n) O(1) O(1)

Inserting an element O(n) O(1) O(1)

Deleting an element O(n) O(1) O(1)

Searching for an O(n) O(1) O(1)


element

Insert (TreeMap) O(log n) O(log n) O(1)

Delete (TreeMap) O(log n) O(log n) O(1)

Maps
Search (TreeMap) O(log n) O(log n) O(1)

(Space-time complexity) Algorithm Complexity:

Time Complexity Space


Complexity
Worst Case Average Case Best Case

Bucket Sort O(n2) O(n + k) O(n + k) O(n)


(k = buckets)

Insertion Sort O(n2) O(n2) O(n) O(1)

Selection Sort O(n2) O(n2) O(n2) O(1)

Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)

Hash-based Search O(n) O(1) O(1) O(1)

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

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

Rabin-Karp Algorithm O(m*(n-m+1)) O(n + m) O(m) O(m)


Time complexity:

Worst Case Average Case Best Case Scenario


Scenario Scenario

Insert O(log n) O(logn) O(1)

Delete O(log n) O(log n) O(1)

Find min/max O(1) O(1) O(1)

Search O(n) O(n) O(1)

Insert O(log n) O(1) O(1)


(Fibonacci/Binomial)

Increase/Decrease key O(log n) O(log n) O(1)

Heaps Extract min/max O(log n) O(log n) O(log n)

(Space-time complexity)

Algorithm Complexity:

Time Complexity Space


Complexity
Worst Case Average Best Case
Case

Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)

Smoothsort O(n log(n)) O(n log(n)) O(n) O(n)

Quick select O(n2) O(n) O(n) O(1)

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

Dijkstra’s shortest O(V2) O(E * log(V)) O(E * log(V)) O(V)


path

You might also like