Learn Guide | TK Premier

O(1): Time complexity of a function with no loops, recursion, and call to any other non-constant function. A loop or recursion that runs a constant number of times is also considered as O(1).

O(n): Time complexity of a loop is considered as O(n) if the loop variables are incremented/decremented by a constant amt. Example:


              // c is inc/dec constant
            for (let i = 0; i < n; i += c) {
              // some O(1) expression
            }
            for (let i = n; i > 0; i -= c) {
              // some O(1) expression
            }

O(n^c): Time complexity of nested loops is equal to the number of times the innermost statement is executed. Example:


            // c is inc/dec constant
            for (let i = 0; i < n; i += c) {
              for (let j = 0; j < n; j += c) {
                // some O(1) expression
              }
            }
            for (let i = n; i > 0; i -= c) {
              for (let j = n; j > 0; j -= c) {
                // some O(1) expression
              }
            }

Selection Sort and Insertion Sort have O(n²) time complexity.

O(Log_n): Time complexity of loop is considered as O(Log_n) if the loop variables are divided/multiplied by a constant amount. And also for a recursive call in recursive function:


            // c is inc/dec constant
            for (let i = 0; i < n; i *= c) {
              // some O(1) expression
            }
            for (let i = n; i > 0; i /= c) {
              // some O(1) expression
            }


            // recursive function
            const recursive = (n) => {
              if (n === 0) return;
              // some O(1) expression
              recurseive(n-1);
            }

Binary Search(iterative implementation) has O(Log_n) time complexity.

The series that we get in the first loop is 1, c, c², c³, ... c^k. If we put k equals to Log_cn, we get c^Log_cn, which is n. 🤷‍♂

O(Log_{Log_n}): Time complexity of loop is considered as O(Log_{Log_n}) if the loop variables are reduced/increased exponentially by a constant amount.


            // c is constant greater than one
            for (let i = 2; i <- n; i = Math.pow(i, c)) {
              // some O(1) expression
            }
            for (let i = n; i > 0; i /= c) {
              // some O(1) expression
            }

More info

Time complexities of consecutive loops are calculated as sum of time complexities in invidual loops.

Sorting Algorithms
1. Selection Sort
```
const swap = (arr, xp, yp) => {
  let temp = arr[xp];
  arr[xp] = arr[yp];
  arr[yp] = temp;
};

export const selectionSort = (arr = []) => {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    let minIndex = i;
    // let minString = arr[i];
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        // minString = arr[j];
        minIndex = j;
      }
    }
    // Swapping the minimum element
    // found with the first element.
    if (minIndex !== i) {
      swap(arr, minIndex, i);
    }
  }
  return arr;
};

export const selectionSortString = (arr = []) => {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    let minIndex = i;
    let minString = arr[i];
    for (let j = i + 1; j < n; j++) {
      if (arr[j].localeCompare(minString) === -1) {
        minString = arr[j];
        minIndex = j;
      }
    }
    // Swapping the minimum element
    // found with the first element.
    if (minIndex !== i) {
      swap(arr, minIndex, i);
    }
  }
  return arr;
};
```
  Complexity Analysis of Selection Sort:
  Time Complexity: O(N²) as there are two nested loops:
  - One loop to select an element of Array one by one = O(N)
  - Another loop to compare that element with every other Array element = O(N)
  - Therefore overall complexity = O(N)*O(N) = O(N*N) = O(N²)
  Auxillary Space: O(1) as the only extra memory used is for temp variable while swapping two values in array. The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.
  Source
2. Bubble Sort
```
export const bubbleSort = (arr = []) => {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
  return arr;
};
```
  Source
3. Insertion Sort
```
export const insertionSort = (arr = []) => {
  for (let i = 0; i < arr.length; i++) {
    let val = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > val) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = val;
  }
  return arr;
};
```
  Source
4. Merge Sort (Source)
  The array is initially divided into two equal halves and then they are combined in a sorted manner.
  We can think of it as a recursive algorithm that continuously splits the array in half until it cannot be further divided. This means that if the array becomes empty or has only one element left, the dividing will stop, i.e. it is the base case to stop the recursion.
  If the array has multiple elements, we split the array into halves and recursively invoke the merge sort on each of the halves. Finally, when both the halves are sorted, the merge operation is applied.
  Merge operation is the process of taking two smaller sorted arrays and combining them to eventually make a larger one.
  Pseudocode
  - Declare
```
left
```
    variable to 0 and
```
right
```
    variable to n-1
  - Find mid by medium formula.
```
mid = (left + right)/2
```
  - Call
```
merge sort
```
    on
```
(left,mid)
```
  - Call
```
merge sort
```
    on
```
(mid+1,right)
```
  - Continue until
```
left < right
```
  - Then call merge function to perform merge sort.
  Algorithm
  1. start
  2. declare array and left, right, mid variable
  3. perform merge function
    mergesort(array, left, right)
    if left > right
    return
    mid= (left+right)/2
    mergesort(array, left, mid)
    mergesort(array, mid+1, right)
    merge(array, left, mid, right)
  4. Stop
  Merge Sort
  Try it out
  Results:
5. QuickSort
6. HeapSort
Searching Algorithms
1. Sequential Search:
  - List is traversed sequentially and every element is searched. Example: Linear Search
  - - Start from leftmost element of array and compare x one by one with each element
    - If x matches, return index
    - If x doesn’t exist, return -1
    - Time Complexity: O(n)
    - Auxiliary Space: O(1)
2. Interval Search:
  - Specifically designed for searching in sorted data-structures.
  - Much more efficient than linear search since they repeatedly target middle of list. Example: Binary Search
  - - Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half, hence binary. The idea of binary search is to use the information that the array is sorted and reduce time complexity to O(Log n).
    - Start with the mid element of the whole array as a search key.
    - If value of the search key (x) matches mid, return index
    - Else If x is lower than mid-el, narrow the interval to lower half and then recur it again.
    - Else narrow the interval to right half and then recur it again.
    - Binary search can be implemented in two ways
      // iterative function binarySearch(arr, x, low, high) { for (let i = low; low < high; i++) { let mid = (i + high)/2; // x equals mid if (x === arr[mid]) { return mid; } if (x > arr[mid]) { i = mid } else { high = mid - 1; } } return mid; }
      // recursive /* l = low r = high x = search item */ export const binaryRecursive = (arr, l, r, x) => { if (r >= 1) { let mid = 1 + Math.floor((r - 1) / 2); // x equals mid if (x === arr[mid]) { return mid; } // if x is smaller than mid, then go left if (arr[mid] > x) { // check previous value to see if x is bigger // then, x does not exist if (x > arr[mid - 1]) { return -1; } return binaryRecursive(arr, l, mid - 1, x); } // if l and r items are the same and the neither value doesn't equal x // exit if (arr[l] === arr[r - 1] && arr[r] !== x) { return -1; } // check last value because it'll never hit last item recursively if (arr[r] === x) { return r; } // else x can only be right return binaryRecursive(arr, mid + 1, r, x); } if (arr[0] === x) { return 0; } return -1; };
      Binary Search
    - Auxiliary Space: O(1)
  - - Interpolation search may go to different locations according to the value of key being searched.
    - The idea of formula is to return higher value of pos when element is considered closer to arr[hi] and smaller vallue when closer to arr[low];
    - pos = lo + (((x - arr[lo]) * (hi - lo))/(arr[hi] - arr[lo]))
      arr[] ==> array to be searched
      x ==> Element to be searched
      lo ==> Starting index in arr
      hi ==> Ending index in arr
    - Many different Interpolation methods. For Example: Linear Interplation.
      Linear interpolation takes two data points which we assume as (x1, y1) and (x2, y2) and the formula is : at point(x, y)
      General equation of line : y = m*x + c.
      y is the value in the array and x is its index.
      
      Now putting value of lo, hi and x in the equation
      arr[hi] = m*hi+c ----(1)
      arr[lo] = m*lo+c ----(2)
      x = m*pos+c ----(3)
      
      m = (arr[hi] - arr[lo] )/ (hi - lo)
      
      subtracting eqn (2) from (3)
      x - arr[lo] = m * (pos - lo)
      lo + (x - arr[lo])/m = pos
      pos = lo + (x - arr[lo]) *(hi - lo)/(arr[hi] - arr\lo)
    - Go to page
    - Auxiliary Space: O(1)
3. Insertion Sort
4. Merge Sort
5. QuickSort
6. HeapSort
Pattern Searching

Learn Guide | TK Premier

Selection Sort

Bubble Sort

Insertion Sort

Merge Sort (Source)

Pseudocode

Algorithm

Merge Sort