complexity.md

COMPLEXITY

This page contains the complexities of different algorithms in this repository.

INDEX

• ALGORITHMS

  • ITERATIVE
    • SEARCHING
      • LINEAR SEARCH
      • BINARY SEARCH
    • PATTERN SEARCHING
    • SORTING
      • BUBBLE SORT
      • SELECTION SORT
      • INSERTION SORT
      • SHELL SORT
      • MERGE SORT
      • QUICK SORT
      • COUNTING SORT
      • RADIX SORT
    • STRINGS
    • BITWISE
    • MATHEMATICAL
    • GEOMETRIC
    • RANDOMIZED
    • DIVIDE AND CONQUER
    • BRANCH AND BOUND
    • GRAPHS
    • GREEDY
    • DYNAMIC PROGRAMMING
    • GAME THEORY
    • MISC
  • RECURSIVE
    • SEARCHING
      • LINEAR SEARCH
      • BINARY SEARCH
    • PATTERN SEARCHING
    • SORTING
    • STRINGS
    • BITWISE
    • MATHEMATICAL
    • GEOMETRIC
    • RANDOMIZED
    • DIVIDE AND CONQUER
    • BRANCH AND BOUND
    • GRAPHS
    • GREEDY
    • DYNAMIC PROGRAMMING
    • GAME THEORY
    • MISC

• DATA STRUCTURES

  • ARRAYS
    • 1D ARRAY
    • 2D ARRAY
    • 3D ARRAY
    • 4D ARRAY
    • INBUILT ARRAY CLASSES
      • ARRAYS CLASS IN JAVA
      • ARRAY CLASS IN C++
    • MISC ARRAYS
      • HEAPED 1D ARRAY
      • HEAPED 2D ARRAY
      • HEAPED 3D ARRAY
      • JAGGED ARRAY
  • STRING
    • Strings in C
    • Strings in C++
    • Strings in JAVA
  • LISTS
    • SINGLE
      • SINGULAR LINKED LIST
      • HYBRID SINGULAR LINKED LIST
    • DOUBLE
      • DOUBLE LINKED LIST
      • HYBRID DOUBLE LINKED LIST
    • CIRCULAR
      • STANDARD CIRCULAR LINKED LIST
      • CIRCULAR LINKED LIST VARIANT 1
    • MEMORY EFFICIENT DOUBLE LINKED LIST
    • UNROLLED LINKED LIST
    • SKIP LIST
    • INBUILT LISTS
      • LINKED LIST
      • ARRAYLISTS
      • VECTORS
    • MISC LISTS
      • Find the nth node from end in single linked list
  • STACKS
    • FIXED ARRAY STACK
    • DYNAMIC ARRAY STACK
    • LINKED STACK
    • INBUILT STACK
      • JAVA
      • C++
    • MISC STACKS
      • [BracketsBalancedOrNot]
  • QUEUES
    • SIMPLE QUEUE
      • FIXED ARRAY SIMPLE QUEUE
      • DYNAMIC ARRAY SIMPLE QUEUE
      • LINKED SIMPLE QUEUE
    • CIRCULAR QUEUE
      • FIXED ARRAY CIRCULAR QUEUE
      • LINKED CIRCULAR QUEUE
    • PRIORITY QUEUE
      • FIXED ARRAY PRIORITY QUEUE
      • LINKED PRIORITY QUEUE
      • HEAPED PRIORITY QUEUE
  • HASHTABLE
  • TREES
    • BINARY TREE
    • GENERIC TREES
    • THREADED BINARY TREE
    • XOR TREES
    • BINARY SEARCH TREE
    • AVL TREES
    • RED BLACK TREES
    • SPLAY TREES
    • AUGMENTED TREES
    • SCAPEGOAT TREES
    • INTERVAL TREES
    • HEAP TREE
  • GRAPHS
  • BLOCKCHAIN

ALGORITHMS

ITERATIVE

🚀 SEARCHING

SNo.	Algorithm	Order of complexity O(n)	Type of Complexity	Iterative
1	Linear Search	O(n)	Linear	✔️
2	Binary Search	O(log n)	Logarithmic	✔️

🚀 PATTERN SEARCHING

🚀 SORTING

SNo.	Algorithm	Order and type of Time complexity O(n)	Order and Type of Space Complexity	Stable/Unstable Sort	In Place Algorithm
1	Bubble Sort	O(n^2) -- Quadratic	O(1) -- Constant	Stable / Can be Unstable**	✔️
2	Selection Sort	O(n^2) -- Quadratic	O(1) -- Constant	Unstable	✔️
3	Insertion Sort	O(n^2) -- Quadratic	O(1) -- Constant	Stable	✔️
4	Shell Sort	O(n^2) or better -- Quadratic or other		Unstable	✔️
5	Counting Sort	O(n) -- Linear		Stable / Unstable	✖️
6	Radix Sort	O(n) or slower than O(nlogn) -- Linear / Logarithmic		Stable	Can Be

**Not an efficient Way

🚀 STRINGS

🚀 BITWISE

🚀 MATHEMATICAL

🚀 GEOMETRIC

🚀 RANDOMIZED

🚀 DIVIDE AND CONQUER

🚀 BRANCH AND BOUND

🚀 GRAPHS

🚀 GREEDY

🚀 DYNAMIC PROGRAMMING

🚀 GAME THEORY

🚀 MISC

RECURSIVE

🔁 SEARCHING

SNo.	Algorithm	Order of complexity O(n)	Type of Complexity	Recursive
1	Linear Search	O(n)	Linear	✔️
2	Binary Search	O(log n)	Logarithmic	✔️

🔁 PATTERN SEARCHING

🔁 SORTING

SNo.	Algorithm	Order of complexity O(n)	Type of Complexity	Stable/Unstable Sort	In Place Algorithm	Space Complexity
1	Merge Sort	O(n logn)	Logarithmic	Stable	✖️
2	Quick Sort	O(n logn)	Logarithmic	Unstable	✔️

🔁 STRINGS

🔁 BITWISE

🔁 MATHEMATICAL

🔁 GEOMETRIC

🔁 RANDOMIZED

🔁 DIVIDE AND CONQUER

🔁 BRANCH AND BOUND

🔁 GRAPHS

🔁 GREEDY

🔁 DYNAMIC PROGRAMMING

🔁 GAME THEORY

🔁 MISC

DATA STRUCTURES

ARRAYS

1D ARRAY

SNo.	Operations	Order of complexity O(n)	Type of Complexity
1	Use value by indexes	O(1)	Constant
2	Insertion at beginning	O(n)	Linear
3	Deletion at beginning	O(n)	Linear
4	Insertion at end (empty array)	O(1)	Constant
5	Deletion at end (empty array)	O(1)	Constant
6	Deletion of the value without having index	O(n)	Linear
7	Update value without having index	O(n)	Linear
8	Update value having index	O(1)	Constant

2D ARRAY

SNo.	Operations	Order of complexity O(n)	Type of Complexity
1	Use value by indexes	O(1)	Constant
2	Insertion at beginning	O(n^2)	Quadratic
3	Deletion at beginning	O(n^2)	Quadratic
4	Insertion at end (empty array)	O(1)	Constant
5	Deletion at end (empty array)	O(1)	Constant
6	Deletion of the value without having index	O(n^n)	Quadratic
7	Update value without having index	O(n^2)	Quadratic
8	Update value having index	O(1)	Constant

3D ARRAY

SNo.	Operations	Order of complexity O(n)	Type of Complexity
1	Use value by indexes	O(1)	Constant
2	Insertion at beginning	O(n^3)	Cubic
3	Deletion at beginning	O(n^3)	Cubic
4	Insertion at end (empty array)	O(1)	Constant
5	Deletion at end (empty array)	O(1)	Constant
6	Deletion of the value without having index	O(n^3)	Cubic
7	Update value without having index	O(n^3)	Cubic
8	Update value having index	O(1)	Constant

4D ARRAY

SNo.	Operations	Order of complexity O(n)	Type of Complexity
1	Use value by indexes	O(1)	Constant
2	Insertion at beginning	O(n^4)	Quadratic
3	Deletion at beginning	O(n^4)	Quadratic
4	Insertion at end (empty array)	O(1)	Constant
5	Deletion at end (empty array)	O(1)	Constant
6	Deletion of the value without having index	O(n^4)	Quadratic
7	Update value without having index	O(n^4)	Quadratic
8	Update value having index	O(1)	Constant

MISC ARRAYS

HEAPED 1D ARRAYS

SNo.	Operations	Order of complexity O(n)	Type of Complexity
1	Use value by indexes	O(1)	Constant
2	Insertion at beginning	O(n)	Linear
3	Deletion at beginning	O(n)	Linear
4	Insertion at end (empty array)	O(n)	Linear
5	Deletion at end (empty array)	O(n)	Linear
6	Deletion of the value without having index	O(n)	Linear
7	Update value without having index	O(n)	Linear
8	Update value having index	O(1)	Constant

HEAPED 2D ARRAYS

SNo.	Operations	Order of complexity O(n)	Type of Complexity
1	Use value by indexes	O(1)	Constant
2	Insertion at beginning	O(n^2)	Quadratic
3	Deletion at beginning	O(n^2)	Quadratic
4	Insertion at end (empty array)	O(n^2)	Quadratic
5	Deletion at end (empty array)	O(n^2)	Quadratic
6	Deletion of the value without having index	O(n^2)	Quadratic
7	Update value without having index	O(n^2)	Quadratic
8	Update value having index	O(1)	Constant

HEAPED 3D ARRAYS

SNo.	Operations	Order of complexity O(n)	Type of Complexity
1	Use value by indexes	O(1)	Constant
2	Insertion at beginning	O(n^3)	Cubic
3	Deletion at beginning	O(n^3)	Cubic
4	Insertion at end (empty array)	O(n^3)	Cubic
5	Deletion at end (empty array)	O(n^3)	Cubic
6	Deletion of the value without having index	O(n^3)	Cubic
7	Update value without having index	O(n^3)	Cubic
8	Update value having index	O(1)	Constant

JAGGED ARRAYS

INBUILT ARRAY CLASSES

ARRAYS CLASS IN JAVA

SNo.	Methods	Order of complexity O(n)	Type of Complexity
1	equals()	O(n)	Linear
2	toString()	O(n)	Linear
3	fill()	O(n)	Linear
4	sort()	O(n logn)	LinearLogarithmic
5	binarySearch()	O(log n)	Logarithmic
6	copyOf()	O(n)	Linear

ARRAY CLASS IN C++

STRING

Strings in C

Strings in CPP

Strings in JAVA

SNo. | Methods | Order of complexity O(n) | Type of Complexity 1 | char charAt() | O(1) | Constant 2 | int indexOf() | O(n) | Linear 3 | lastIndexOf() | O(n) | Linear 4 | int length() | O(1) | Constant 5 | substring() | O(n) | Linear 6 | replace() | O(n) | Linear 7 | concat(str) | O(n^2) | Quadratic 8 | equals(str) | O(n) | Linear 9 | toUpperCase() | O(n) | Linear 10 | toLowerCase() | O(n) | Linear

LISTS

SINGLE

SINGULAR LINKED LIST (having head and next)

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Traversing a list	O(n) -- Linear	O(1) -- Constant
2	Insertion at Head	O(1) -- Constant	O(1) -- Constant
3	Insertion at Tail	O(n) -- Linear	O(1) -- Constant
4	Insertion at Middle using Position	O(n) -- Linear	O(1) -- Constant
5	Insertion at Middle Exactly	O(n/2) -- Linear	O(1) -- Constant
6	Deletion from Head	O(1) -- Constant	O(1) -- Constant
7	Deletion from Tail	O(n) -- Linear	O(1) -- Constant
8	Deletion from Middle using Position	O(n) -- Linear	O(1) -- Constant
9	Deletion from Middle using Value	O(n) -- Linear	O(1) -- Constant
10	Deletion from Middle Exactly	O(n/2) -- Linear	O(1) -- Constant
11	Linear Search	O(n) -- Linear	O(1) -- Constant
12	Clear list	O(1) -- Constant	O(1) -- Constant

HYBRID SINGULAR LINKED LIST (having head,tail and next)

DOUBLE

DOUBLE LINKED LIST (having head,tail and next,prev)

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Traversing a list (from left or right)	O(n) -- Linear	O(1) -- Constant
2	Insertion at Head	O(1) -- Constant	O(1) -- Constant
3	Insertion at Tail	O(1) -- Constant	O(1) -- Constant
4	Insertion at Middle using Position	O(n) -- Linear	O(1) -- Constant
5	Insertion at Middle Exactly	O(n/2) -- Linear	O(1) -- Constant
6	Deletion from Head	O(1) -- Constant	O(1) -- Constant
7	Deletion from Tail	O(1) -- Constant	O(1) -- Constant
8	Deletion from Middle using Position	O(n) -- Linear	O(1) -- Constant
9	Deletion from Middle using Value	O(n) -- Linear	O(1) -- Constant
10	Deletion from Middle Exactly	O(n/2) -- Linear	O(1) -- Constant
11	Linear search	O(n) -- Linear	O(1) -- Constant
12	Clear list	O(1) -- Constant	O(1) -- Constant
13	Optimal Search	O(n/2) -- Linear	O(1) -- Constant

HYBRID DOUBLE LINKED LIST (having head,prev and next)

CIRCULAR

STANDARD CIRCULAR LINKED LIST

(having tail ,next and loop)

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Traversing a list (from left to right to head)	O(n) -- Linear	O(1) -- Constant
2	Insertion at Head	O(1) -- Constant	O(1) -- Constant
3	Insertion at Tail	O(1) -- Constant	O(1) -- Constant
4	Deletion from Head	O(1) -- Constant	O(1) -- Constant
5	Deletion from Tail	O(n) -- Linear	O(1) -- Constant
6	Deletion from middle using value	O(n) -- Linear	O(1) -- Constant
6	Linear search	O(n) -- Linear	O(1) -- Constant
7	Clear list	O(1) -- Constant	O(1) -- Constant

CIRCULAR LINKED LIST VARIANT 1

(having head ,next and loop)

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Traversing a list (from left to right to head)	O(n) -- Linear	O(1) -- Constant
2	Insertion at Head	O(n) -- Linear	O(1) -- Constant
3	Insertion at Tail	O(n) -- Linear	O(1) -- Constant
4	Insertion at Middle	O(n) -- Linear	O(1) -- Constant
4	Deletion from Head	O(n) -- Linear	O(1) -- Constant
5	Deletion from Tail	O(n) -- Linear	O(1) -- Constant
6	Deletion from middle	O(n) -- Linear	O(1) -- Constant
7	Linear search	O(n) -- Linear	O(1) -- Constant
8	Clear list	O(1) -- Constant	O(1) -- Constant
9	Length of list	O(1) -- Constant	O(1) -- Constant

MEMORY EFFICIENT (XOR) DOUBLE LINKED LIST

UNROLLED LINKED LIST

SKIP LIST

INBUILT LISTS

ARRAYLISTS (JAVA)

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Traversing a list	O(n) -- Linear	O(1) -- Constant
2	add(element) -- Insertion at Tail	O(1) -- Constant	O(1) -- Constant
3	add(index,element) -- Insertion at Middle using index	O(n) -- Linear	O(1) -- Constant
4	remove(index) -- Deletion from Middle using index	O(n) -- Linear	O(1) -- Constant
5	contains(element) -- Search List	O(n) -- Linear	O(1) -- Constant
6	get(index) -- Accessing random element	O(1) -- Constant	O(1) -- Constant

VECTORS (C++,JAVA)

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity

MISC LISTS

Find the nth node from end in single linked list

SNo.	APPROACH	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Compute the size while adding	O(n) -- Linear	O(1) -- Constant
2	Using two current pointers	O(n^2) -- Quadratic	O(1) -- Constant
3	Using hashtable	O(n) -- Linear	O(n) -- Linear
4	Using Hashtable while adding	O(1) -- Constant	O(n) -- Linear
5	Finding node in one scan	O(n) -- Linear	O(1) -- Constant
6	Using recursion	O(n) -- Linear	O(n) -- Linear

STACKS

FIXED ARRAY STACK

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Push an element or Insert element	O(1) -- Constant	O(1) -- Constant
2	Pop an element or Delete element	O(1) -- Constant	O(1) -- Constant
3	Get value of top	O(1) -- Constant	O(1) -- Constant
4	Is empty or not	O(1) -- Constant	O(1) -- Constant
5	Printing the stack	O(n) -- Linear	O(1) -- Constant

DYNAMIC ARRAY STACK

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Push an element or Insert element	O(n) -- Linear	O(log(n)) -- Logarithmic
2	Pop an element or Delete element	O(1) -- Constant	O(1) -- Constant
3	Get value of top	O(1) -- Constant	O(1) -- Constant
4	Is empty or not	O(1) -- Constant	O(1) -- Constant
5	Printing the stack	O(n) -- Linear	O(1) -- Constant

LINKED STACK

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Push an element or Insert element	O(1) -- Constant	O(1) -- Constant
2	Pop an element or Delete element	O(1) -- Constant	O(1) -- Constant
3	Get value of top	O(1) -- Constant	O(1) -- Constant
4	Is empty or not	O(1) -- Constant	O(1) -- Constant
5	Printing the stack/deletestack	O(n) -- Linear	O(1) -- Constant

INBUILT STACK

MISC STACKS

QUEUES

SIMPLE QUEUE

FIXED ARRAY SIMPLE QUEUE

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Enqueue an element or Insert element	O(1) -- Constant	O(1) -- Constant
2	Dequeue an element or Delete element	O(1) -- Constant	O(1) -- Constant
3	Print the queue	O(n) -- Linear	O(1) -- Constant
4	Size of the queue	O(1) -- Constant	O(1) -- Constant
5	Queue is Empty or not	O(1) -- Constant	O(1) -- Constant

DYNAMIC ARRAY SIMPLE QUEUE

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Enqueue an element or Insert element	O(1) -- Constant	O(log n) -- Logarthmic
2	Dequeue an element or Delete element	O(1) -- Constant	O(1) -- Constant
3	Print the queue	O(n) -- Linear	O(1) -- Constant
4	Size of the queue	O(1) -- Constant	O(1) -- Constant
5	Queue is Empty or not	O(1) -- Constant	O(1) -- Constant

LINKED SIMPLE QUEUE

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Enqueue an element or Insert element	O(n) -- Linear	O(1) -- Constant
2	Dequeue an element or Delete element	O(1) -- Constant	O(1) -- Constant
3	Print the queue	O(n) -- Linear	O(1) -- Constant
4	Size of the queue	O(1) -- Constant	O(1) -- Constant
5	Queue is Empty or not	O(1) -- Constant	O(1) -- Constant

CIRCULAR QUEUE

FIXED ARRAY CIRCULAR QUEUE

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Enqueue an element or Insert element	O(1) -- Constant	O(1) -- Constant
2	Dequeue an element or Delete element	O(1) -- Constant	O(1) -- Constant
3	Print the queue	O(n) -- Linear	O(1) -- Constant
4	Size of the queue	O(1) -- Constant	O(1) -- Constant
5	Queue is Empty or not	O(1) -- Constant	O(1) -- Constant

LINKED CIRCULAR QUEUE

PRIORITY QUEUE

FIXED ARRAY PRIORITY QUEUE

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Insert element with priority	O(n) -- Linear	O(1) -- Constant
2	Delete element with highest priority	O(n) -- Constant	O(1) -- Constant
3	Print the queue	O(n) -- Linear	O(1) -- Constant
4	Size of the queue	O(1) -- Constant	O(1) -- Constant
5	Queue is Empty or not	O(1) -- Constant	O(1) -- Constant

LINKED PRIORITY QUEUE

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity
1	Insert element with priority	O(n) -- Linear	O(1) -- Constant
2	Delete element with highest priority	O(1) -- Constant	O(1) -- Constant
3	Print the queue	O(n) -- Linear	O(1) -- Constant
4	Size of the queue	O(1) -- Constant	O(1) -- Constant
5	Queue is Empty or not	O(1) -- Constant	O(1) -- Constant

HEAPED PRIORITY QUEUE

HASHTABLE

TREES

BINARY TREES

SNo.	Operations	Order and Type of Time Complexity O(n)	Order and Type of Space Complexity	Iterative	Recursive
1	In Order Traversal	O(n) -- Linear	O(n) -- Linear	✔️	✔️
2	Pre Order Traversal	O(n) -- Linear	O(n) -- Linear	✔️	✔️
3	Post Order Traversal	O(n) -- Linear	O(n) -- Linear	✔️	✔️
4	Level Order Traversal	O(n) -- Linear	O(n) -- Linear	✔️	❌
5	Bottom View of a Tree	O(n) -- Linear	O(n) -- Linear	✔️	❌

GENERIC TREES

THREADED BINARY TREE

XOR TREES

BINARY SEARCH TREE

AVL TREES

RED BLACK TREES

SPLAY TREES

AUGMENTED TREES

SCAPEGOAT TREES

INTERVAL TREES

HEAP TREE

GRAPHS

BLOCKCHAIN