Data-Structures-and-Algorithms

Big - O Notation

Notation	Name
O(1)	Constant
O(logn)	Logarithmic
O(n)	Linear
O(nlogn)	n log-star n
O(n^2)	Quadratic

Array

Operation	Time Complexity
Retrieve with index.	O(1) - Constant time
Retrieve without index.	O(n) - Linear time
Add an element to full array.	O(n) - Linear time
Add an element to the end of an array. (has space)	O(1) - Constant time
Insert or update an element at a specific index.	O(1) - Constant time
Delete an element by setting it to null.	O(1) - Constant time
Delete an element by shifting elements.	O(n) - Linear time

Time Complexities of all Sorting Algorithms

Bubble Sort

Performance	Time Complexity
Worst Case	O(n^2) - Quadratic time
Avarage Case	O(n^2) - Quadratic time
Best Case	O(n) - Linear time

Selection Sort

Performance	Time Complexity
Worst Case	O(n^2) - Quadratic time
Avarage Case	O(n^2) - Quadratic time
Best Case	O(n^2) - Quadratic time

Insertion Sort

Performance	Time Complexity
Worst Case	O(n^2) - Quadratic time
Avarage Case	O(n^2) - Quadratic time
Best Case	O(n) - Linear time

Shell Sort

Performance	Time Complexity
Worst Case	O(n^2) - Quadratic time
Avarage Case	O(nlogn) - n log-star n
Best Case	O(nlogn) - n log-star n

Merge Sort

Performance	Time Complexity
Worst Case	O(nlogn) - n log-star n
Avarage Case	O(nlogn) - n log-star n
Best Case	O(nlogn) - n log-star n

Quick Sort

Performance	Time Complexity
Worst Case	O(n^2) - Quadratic time
Avarage Case	O(nlogn) - n log-star n
Best Case	O(nlogn) - n log-star n

Counting Sort

Performance	Time Complexity
Worst Case	O(n+k)
Avarage Case	O(n+k)
Best Case	O(n+k)

Radix Sort

Performance	Time Complexity
Worst Case	O(kn)
Avarage Case	O(kn)
Best Case	O(kn)

Performance analysis of ArrayList, LinkedList and Vector

ArrayList

Operation	Time Complexity
Insert at last index	O(1) --> If array copy operation is Considered then O(n)
Insert at given index	O(n)
Search by value	O(n) ( Preferred )
Get by index	O(1) ( Preferred )
Remove by value	O(n)
Remove by index	O(n)

ArrayList<Employee> employees = new ArrayList<>();

LinkedList

Operation	Time Complexity
Insert at last index	O(1) ( Preferred )
Insert at given index	O(n) ( Preferred )
Search by value	O(n)
Get by index	O(n)
Remove by value	O(n) ( Preferred )
Remove by index	O(n) ( Preferred )

LinkedList<Employee> employees= new LinkedList<>();

Vector

Vector : Unlike the new collection implementations, Vector is synchronized. If a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector.

Performance: ArrayList is faster, since it is non-synchronized, while vector operations give slower performance since they are synchronized (thread-safe).

Vector<Employee> employees = new Vector<>();

Stack

LIFO (Last-in-first-out)

ArrayStack

Operation	Time Complexity
Push	O(n)
Pop	O(1)
Peek	O(1)

LinkedStack

Operation	Time Complexity
Push	O(1)
Pop	O(1)
Peek	O(1)

Search Algorithms

Linear Search

Operation	Time Complexity
Search	O(n)

Binary Search

Operation	Time Complexity
Search	O(logn)

Queue

FIFO (First-in-first-out)

Array implementation of queue

Operation	Time Complexity
Add	O(1)
Remove	O(n)
Peek	O(1)

LinkedList implementation of queue

Operation	Time Complexity
Add	O(1)
Remove	O(1)
Peek	O(1)

Binary Search Tree ( BST )

Operation	Time Complexity
Insertion	O(logn)
Deletion	O(logn)
Retrieval	O(logn)