top of page

Subscribe to Wisdom

Thanks for Subscribing!

  • Writer's picturePuru Uttam

Time & Space Complexity

Time Complexity is the amount of time taken by an algorithm for each of it's statement to complete the execution. As a result, it is highly dependent on the size of the processed data. It is helpful in defining an algorithm's effectiveness and evaluating its performance.


Space Complexity is the total amount of memory space taken by a program for it's execution. It includes storing input data and temporary values while execution of a program. Basically for variables, inputs, and outputs.

Auxiliary space + Input data space = Space Complexity

Here are all the time and space complexities listed below. Mainly Big-Oh (O) notation is used here for the representation.

Asymptotic notations are classified into three types:
1. Big-Oh (O) notation
2. Big Omega ( Ω ) notation
3. Big Theta ( Θ ) notation


Sorting & Searching:

Type of Sorting

Best Case

Average Case

Worst Case

Space Complexity

Selection Sort

O(n^2)

O(n^2)

O(n^2)

O(1)

Insertion Sort

O(n)

O(n^2)

O(n^2)

O(1)

Bubble Sort

O(n)

O(n^2)

O(n^2)

O(1)

Merge Sort

O(n log(n))

O(n log(n))

O(n log(n))

O(n)

Quick Sort

O(n log(n))

O(n log(n))

O(n^2)

O(log(n))

Bucket Sort

O(n+k)

O(n+k)

O(n^2)

O(n)

Heap Sort

O(n log(n))

O(n log(n))

O(n log(n))

O(1)

Radix Sort

O(nk)

O(nk)

O(nk)

O(n+k)

Count Sort

O(n+k)

O(n+k)

O(n^2)

O(k)

Tim Sort

O(n)

O(n log(n))

O(n log(n))

O(n)

Shell Sort

O(n)

O((n log(n))^2)

O((n log(n))^2)

O(1)

Tree Sort

O(n log(n))

O(n log(n))

O(n^2)

O(n)

Cube Sort

O(n)

O(n log(n))

O(n log(n))

O(n)

Linear Search

O(1)

O(n)

O(n)

O(1)

Binary Search

O(1)

O(log(n))

O(log(n))

O(1)


Average Case Complexities :

Data Structure

Insertion

Deletion

Access

Search

Array

O(n)

O(n)

O(1)

O(n)

Stack

O(1)

O(1)

O(n)

O(n)

Queue

O(1)

O(1)

O(n)

O(n)

Singly Linked List

O(1)

O(1)

O(n)

O(n)

Doubly Linked List

O(1)

O(1)

O(n)

O(n)

Hash Table

O(1)

O(1)

O(1)

O(1)

Binary Search Tree

O(log(n))

O(log(n))

O(log(n))

O(log(n))

B- Tree

O(log(n))

O(log(n))

O(log(n))

O(log(n))

Red-Black Tree

O(log(n))

O(log(n))

O(log(n))

O(log(n))

AVL Tree

O(log(n))

O(log(n))

O(log(n))

O(log(n))


Worst Case Complexities :

Data Structure

Insertion

Deletion

Access

Search

Space Complexity

Array

O(n)

O(n)

O(1)

O(n)

O(n)

Stack

O(1)

O(1)

O(n)

O(n)

O(n)

Queue

O(1)

O(1)

O(n)

O(n)

O(n)

Singly Linked List

O(1)

O(1)

O(n)

O(n)

O(n)

Doubly Linked List

O(1)

O(1)

O(n)

O(n)

O(n)

Hash Table

O(n)

O(n)

O(n)

O(n)

O(n)

Binary Search Tree

O(n)

O(n)

O(n)

O(n)

O(n)

B-Tree

O(n)

O(n)

O(n)

O(n)

O(n)

Red-Black Tree

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





19 views0 comments

Recent Posts

See All

Comments


Modern Digital Watch
bottom of page