Showing posts with label best case. Show all posts
Showing posts with label best case. Show all posts

Tuesday, June 02, 2020

Time complexities and asymptotic notation

Searching

Algorithm

Data Structure

Time Complexity

Space Complexity

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,
using a Min-heap as priority queue

Graph with |V| vertices and |E| edges

O((|V| + |E|) log |V|)

O((|V| + |E|) log |V|)

O(|V|)

Shortest path by Dijkstra,
using an unsorted array as priority queue

Graph with |V| vertices and |E| edges

O(|V|^2)

O(|V|^2)

O(|V|)

Shortest path by Bellman-Ford

Graph with |V| vertices and |E| edges

O(|V||E|)

O(|V||E|)

O(|V|)

 

Sorting

Algorithm

Data Structure

Time Complexity

Worst Case Auxiliary Space Complexity

Best

Average

Worst

Worst

Quicksort

Array

O(n log(n))

O(n log(n))

O(n^2)

O(n)

Mergesort

Array

O(n log(n))

O(n log(n))

O(n log(n))

O(n)

Heapsort

Array

O(n log(n))

O(n log(n))

O(n log(n))

O(1)

Bubble Sort

Array

O(n)

O(n^2)

O(n^2)

O(1)

Insertion Sort

Array

O(n)

O(n^2)

O(n^2)

O(1)

Select Sort

Array

O(n^2)

O(n^2)

O(n^2)

O(1)

Bucket Sort

Array

O(n+k)

O(n+k)

O(n^2)

O(nk)

Radix Sort

Array

O(nk)

O(nk)

O(nk)

O(n+k)

 

Heaps

Heaps

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))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

Fibonacci Heap

-

O(1)

O(log(n))*

O(1)*

O(1)

O(log(n))*

O(1)

 

Graphs

Node / Edge Management

Storage

Add Vertex

Add Edge

Remove Vertex

Remove Edge

Query

Adjacency list

O(|V|+|E|)

O(1)

O(1)

O(|V| + |E|)

O(|E|)

O(|V|)

Incidence list

O(|V|+|E|)

O(1)

O(1)

O(|E|)

O(|E|)

O(|E|)

Adjacency matrix

O(|V|^2)

O(|V|^2)

O(1)

O(|V|^2)

O(1)

O(1)

Incidence matrix

O(|V| |E|)

O(|V| |E|)

O(|V| |E|)

O(|V| |E|)

O(|V| |E|)

O(|E|)

 

Data Structures

Data Structure

Time Complexity

Space Complexity

Average

Worst

Worst

Indexing

Search

Insertion

Deletion

Indexing

Search

Insertion

Deletion

Basic Array

O(1)

O(n)

-

-

O(1)

O(n)

-

-

O(n)

Dynamic Array

O(1)

O(n)

O(n)

O(n)

O(1)

O(n)

O(n)

O(n)

O(n)

Singly-Linked List

O(n)

O(n)

O(1)

O(1)

O(n)

O(n)

O(1)

O(1)

O(n)

Doubly-Linked List

O(n)

O(n)

O(1)

O(1)

O(n)

O(n)

O(1)

O(1)

O(n)

Skip List

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(n)

O(n)

O(n)

O(n)

O(n log(n))

Hash Table

-

O(1)

O(1)

O(1)

-

O(n)

O(n)

O(n)

O(n)

Binary Search Tree

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(n)

O(n)

O(n)

O(n)

O(n)

Cartesian Tree

-

O(log(n))

O(log(n))

O(log(n))

-

O(n)

O(n)

O(n)

O(n)

B-Tree

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(n)

Red-Black Tree

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(n)

Splay Tree

-

O(log(n))

O(log(n))

O(log(n))

-

O(log(n))

O(log(n))

O(log(n))

O(n)

AVL Tree

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(n)

 

Notation for asymptotic growth

letter

bound

growth

(theta) Θ

upper and lower, tight[1]

equal[2]

(big-oh) O

upper, tightness unknown

less than or equal[3]

(small-oh) o

upper, not tight

less than

(big omega) Ω

lower, tightness unknown

greater than or equal

(small omega) ω

lower, not tight

greater than


Search Aptipedia