# Problem solving Notes

Big O

If we have two functions and we need to find which is optimal. We can use Big O to find the one.

We can easily classify the functions from Great β Awful

It's not only about make it work we should also care about make it best. Big O will help.

Good to have a vocabulary to talk about how our code performs.

To discuss tradeoff between different approaches

Help to identify the inefficient code causing the crashes.

Timing the code by checking how long it takes to run is a bad idea.

Counting how many operation the function doing is not great. Like calculating the operation of

`a = a*b+c`

this is not good π. We can't calcualte the operation inside look etc.We should calculate the overall calculations.

*We say that an algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n), as n increases*f(n) could be linear (f(n) = n) f(n) could be quadratic (f(n) = n2) f(n) could be constant (f(n) = 1) f(n) could be something entirely different!

O(1) β Runtime won't grow based on the input

`function addUpTo(n) {`

return (n * (n + 1)) / 2;

}

// Always 3 operationsO(n) β Runtime grow based on the input

`function addUpTo(n) {`

let total = 0;

for (let i = 1; i <= n; i++) {}

}

// Number of operations is (eventually) bounded by a

// multiple of n (say, 10n). In short, O(n)`function countUpAndDown(n) {`

for (let i = 0; i < n; i++) {

console.log(i);

}

for (let j = n - 1; j >= 0; j--) {

console.log(j);

}

}

// Number of operations is (evenutally bounded by a multiple of n (say, 10n)

// We can simply by O(n)O(n2) β Runtime grow twice the input

`function printAllPairs(n) {`

for (var i = 0; i < n; i++) {

for (var j = 0; j < n; j++) {

console.log(i, j);

}

}

}

### SImplificationβ

`No matter what input is it'll run exact operation`

O(500) β O(1) so, we can simplify like this.

O(2n) β O(n)

O(13n2) β O(n2)

O(n + 10) β O(n) - n + 10 constant operation will result in O(n)

O(1000n + 50) β O(n)

O(n2 + 5n + 8) β O(n2)

Some more tips:

- Arithmetic operations are constant (adding, sub, div, etc)
- Variable assignment is constant (a =3455, etc)
- Accessing elements in an array (by index) or object (by key) is constant
- In a loop, the complexity is the length of the loop times the complexity of whatever happens inside of the loop

Examples:

`function logAtLeast5(n) {`

for (var i = 1; i <= Math.max(5, n); i++) {

console.log(i);

}

}

// O(n)`function logAtMost5(n) {`

for (var i = 1; i <= Math.min(5, n); i++) {

console.log(i);

}

}

// O(1)

`O(1)`

Β time

`O(1)`

Β timeAccessing Array Index (int a = ARR[5];)

Inserting a node in Linked List

Pushing and Poping on Stack

Insertion and Removal from Queue

Finding out the parent or left/right child of a node in a tree stored in Array

Jumping to Next/Previous element in Doubly Linked List

`O(n)`

Β time

`O(n)`

Β time`In a nutshell, all Brute Force Algorithms, or Noob ones which require linearity, are based on O(n) time complexity`

Traversing an array

Traversing a linked list

Linear Search

Deletion of a specific element in a Linked List (Not sorted)

Comparing two strings

Checking for Palindrome

Counting/Bucket Sort and here too you can find a million more such examples....

`O(log n)`

Β time

`O(log n)`

Β timeBinary Search

Finding largest/smallest number in a binary search tree

Certain Divide and Conquer Algorithms based on Linear functionality

Calculating Fibonacci Numbers - Best Method The basic premise here is NOT using the complete data, and reducing the problem size with every iteration

`O(n log n)`

Β time

`O(n log n)`

Β time`The factor of 'log n' is introduced by bringing into consideration Divide and Conquer. Some of these algorithms are the best optimized ones and used frequently.`

Merge Sort

Heap Sort

Quick Sort

Certain Divide and Conquer Algorithms based on optimizing O(n^2) algorithms

`O(n^2)`

Β time

`O(n^2)`

Β time`These ones are supposed to be the less efficient algorithms if their O(nlogn) counterparts are present. The general application may be Brute Force here.`

- Bubble Sort
- Insertion Sort
- Selection Sort
- Traversing a simple 2D array

## Space Complexityβ

`1. Most primitives (booleans, numbers, undefined, null) are constant space`

2. Strings require O(n) space (where n is the string length)

3. Reference types are generally O(n), where n is the length (for arrays) or the number of keys (for objects)

```jsx

function sum(arr){

let total = 0; // Variable declaration

for (let i = 0; i < arr.length; i++) { // Variable declaration

total += arr[i];

}

return total;

}

// O(1) space

```

```jsx

function double(arr) {

let newArr = []; // Space will grow proportional to the input

for (let i = 0; i < arr.length; i++){

newArr.push(2 * arr[i]);

}

return newArr;

}

// O(n) space

```

Linear Searching

A simple approach is to do aΒ

**linear search**, i.eStart from the leftmost element of arr[] and one by one compare x with each element of arr[]

If x matches with an element, return the index.

If x doesnβt match with any of elements, return -1.

Time Complexity: Best - O(1)

Average - O(n)

Worst - O(n)

Binary Searching

- Binary search is a much faster form of search
- Rather than eliminating one element at a time, you can eliminate half of the remaining elements at a time.
- Binary search only works on sorted arrays!

The idea is Divide and Conquer

**Pseudocode**This function accepts a sorted array and a value

Create a left pointer at the start of the array, and a right pointer at the end of the array.

While the left pointer comes before the right pointer:

- Create a pointer in the middle
- If you find the value you want, return the index
- If the value is too small, move the left pointer up
- If the value is too large, move the right pointer down

If you never find the value, return -1

`function binarySearch(sortedArray, seekElement, comparatorCallback) {`

// Let's create comparator from the comparatorCallback function.

// Comparator object will give us common comparison methods like equal() and lessThen().

const comparator = new Comparator(comparatorCallback);

// These two indices will contain current array (sub-array) boundaries.

let startIndex = 0;

let endIndex = sortedArray.length - 1;

// Let's continue to split array until boundaries are collapsed

// and there is nothing to split anymore.

while (startIndex <= endIndex) {

// Let's calculate the index of the middle element.

const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2);

// If we've found the element just return its position.

if (comparator.equal(sortedArray[middleIndex], seekElement)) {

return middleIndex;

}

// Decide which half to choose for seeking next: left or right one.

if (comparator.lessThan(sortedArray[middleIndex], seekElement)) {

// Go to the right half of the array.

startIndex = middleIndex + 1;

} else {

// Go to the left half of the array.

endIndex = middleIndex - 1;

}

}

// Return -1 if we have not found anything.

return -1;

}

Bubble Sorting

Sorting is an incredibly common task, so it's good to know how it works

There are many different ways to sort things, and different techniques have their own advantages and disadvantages.

**Javascript Sorting:**`["Karthik", "Javascript", "Algorithms"].sort();`

// ['Algorithms', 'Javascript', 'Karthik']

[6, 4, 15, 10].sort();

// [10, 15, 4, 6]The default sort order is according to string Unicode code points. The array is sorted according to each character's Unicode code point value, according to the string conversion of the each element.

The built-in sort method accepts an optional comparator function

You can use this comparator function to tell Javascript how you want it to sort

The comparator looks at pairs of elements (a and b), determine their sort order based on the return value

- If it returns a negative number, a should come before b
- If it returns a positive number, a should come after b,
- If it returns 0, a and b are the same as far as the sort is concerned.

**Bubble sort:**A sorting algorithm where the largest values bubble up to the top!

Psuedocode:

- Start looping from with a variable called i the end of the array towards the beginning
- Start an inner loop with a variable called j from the beginning until i - 1
- If arr[j] is greater than arr[j+1], swap those two values!
- Return the sorted array

`function bubbleSort(arr) {`

var noSwaps;

for (var i = arr.length; i > 0; i--) {

noSwaps = true;

for (var j = 0; j < i - 1; j++) {

if (arr[j] > arr[j + 1]) {

var temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

noSwaps = false;

}

}

if (noSwaps) break;

}

return arr;

}

Selection Sort

Similar to bubble sort, but instead of first placing large values into sorted position, it places small values into sorted position.

**Pseudocode:**- Store the first element as the smallest value you've seen so far.
- Compare this item to the next item in the array until you find a smaller number.
- If a smaller number is found, designate that smaller number to be the new "minimum" and continue until the end of the array.
- If the "minimum" is not the value (index) you initially began with, swap the two values.
- Repeat this with the next element until the array is sorted.

`function selectionSort(arr) {`

for (var i = 0; i < arr.length; i++) {

var lowest = i;

for (var j = i + 1; j < arr.length; j++) {

if (arr[j] < arr[lowest]) {

lowest = j;

}

}

if (i !== lowest) {

var temp = arr[i];

arr[i] = arr[lowest];

arr[lowest] = temp;

}

}

return arr;

}