
Introduction
Common Data structures
- Array
- Linked List
- Stack
- Queue
- HashTable
- Tree
- Heap
- Graph
Space Complexity : Unit space required to store the data.
Time Complexity: Unit time required to complete any algorithm.
- Factorial of a number. = O(n)
- Print a 2D matrix = O(n*2)
- Print number to binary = O(logn)
- Print table of given number = O(1)
- Linear Search = O(n)
for(int i=0; i<arr.length; i++) {
if(key == arr[i])
return i;
}
Here since finding an element depends of length of array hence O(n) is timecomplexity
- Binary Search = O(logn)

//using Loop
public static int binarySearch(int[] arr, int key) {
int left = 0, right = arr.length-1, mid;
while(left <= right) {
mid = (left + right) / 2;
if(key == arr[mid])
return mid;
if(key < arr[mid])
right = mid - 1;
else //(key > arr[mid])
left = mid + 1;
}
return -1;
}
//using Recursion
public static int binarySearch(int[] arr, int left, int right, int key) {
if (left > right)
return -1;
int index, mid = (left + right) / 2;
if (key == arr[mid])
return mid;
if (key < arr[mid])
index = binarySearch(arr, left, mid - 1, key);
else
index = binarySearch(arr, mid + 1, right, key);
return index;
}
Here finding an element depends on
1 = n/2^k
n = 2^k
k = logn
Hence number of iteration required for finding an element is Logn
- Selection Sort = O(n*2)

for(int i=0; i<arr.length-1; i++) {
for(int j=i+1; j<arr.length; j++) {
if(arr[i] < arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
Time Complexity
T > n(n - 1)/ 2 = N Factorial
t = n*2
- Bubble Sort = O(n * 2)

public static void bubbleSort(int[] arr) {
for(int i=0; i<arr.length-1; i++) {
for(int j=0; j<arr.length-1; j++) {
if(arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
TimeComplexity for multiple loops are always n*2
- Insertion Sort = O(n * 2)

public static void insertionSort(int[] arr) {
for(int i=1; i<arr.length; i++) {
int j, temp = arr[i];
for(j=i-1; j >= 0 && arr[j] > temp; j--)
arr[j+1] = arr[j];
arr[j+1] = temp;
}
}