Notes-Section1.txt

# =============================================================== #
# =============================================================== #
SECTION 1 --- Algorithmic complexity / Big-O / Asymptotic analysis
# =============================================================== #
    1) Harvard CS50 - Asymptotic Notation (video)
        --- Watched. Did not take notes.
    # ----------------------------------------------------------- #
    2) Big O Notations (general quick tutorial) - Derek Banas (YouTube)
            + Example 1 Formula (or algorithm)
            45n^3 + 20n^2 + 19 = 84 /// (where n=1)
                    45n^3 + 20n^2 + 19 = 459 /// (where n=2)
                            45n^3 + 20n^2 + 19 = 47,019 /// (where n=10)
                                    45n^3 = 45,000 /// (where n=10)
                + The point of the above is that the part of the algorithm that
                really has a lot to with the final answer as the dataset scales,
                is going to be the n^3 (as opposed to the 19, or even the n^2).
                Therefore, the above algorithm has an 'order of N cubed' ---> O(n^3)

            + The following big O notations will be covered in this video:
              O(1)
              O(n)
              O(n^2)
              O(log n)
              O(n log n)

            + Let's do it in code! (Example in Java)

            public class BigONotation {

                private int[] theArray;
                private int arraySize;
                private int itemsInArray = 0;

                public static void main(String[] args) {


                }

                // O(1) --- 'Constant time'
                // ====================================
                // This notation means the algorithm will take the same
                // amount of time to execute no matter how big the input is.

                // Example: Add an item to our array...

                public void addItemtoArray(int newItem){

                theArray[itemsInArray++] = newItem;

                }

                // O(n) --- 'Linear time'
                // ====================================
                // This algorithm's execution time will grow in
                // direct proportion to the size of the input.

                // Example: Linear search...

                public void linearSearchForValue(int value){

                    boolean valueInArray = false;
                    String indexsWithValue = "";

                    for(int i = 0; i < arraySize; i++){

                        if(theArray[i] == value){

                            valueInArray = true;
                            indexsWithValue += i + " ";
                        }
                    }

                    System.out.println("Value Found: " + valueInArray);
                }

                // O(n^2) --- 'Quadratic time'
                // ====================================
                // The execution time of this notation will
                // grow in proportion to the square of the input.
                // (e.g. - nested loops)

                // Example: Bubble sort...

                public void bubblesort(){

                    for(int i = arraySize - 1; i > 1; i--){

                        for(int j = 0; j < i; j++){

                            if theArray[j] > theArray[j+1]){

                                swapValues(j, j+1);
                            }
                        }
                    }
                }

                // O(log n) --- 'Logarithmic time'
                // ====================================
                // In this notation, as n increases, log(n) increases
                // to a much lower degree than n itself.

                // Example: Binary search...

                public void binarySearchForValue(int value){

                    int lowIndex = 0;
                    int highIndex = arraySize -1;

                    while(lowIndex <= highIndex){

                        int middleIndex = (highIndex + lowIndex) / 2;

                        if(theArray[middleIndex] < value)
                            lowIndex = middleIndex + 1;

                        else if(theArray[middleIndex] > value)
                            highIndex = middleIndex - 1;

                        else {

                            System.out.println("Found Match in index " + middleIndex);
                            lowIndex = highIndex + 1;
                        }
                    }
                }

                // O(n log n) --- 'Linearithmic time'
                // ====================================
                // This time notation is going to be faster than quadratic O(n^2)
                // but slower than logarithmic O(log n) or linear O(n); it's
                // common in efficient sorting algorithms (e.g. - merge sort)
                // and, more generally, in any algo's that use recursion.

                // Example: Quicksort...

                public void quickSort(int left, int right){

                    if(right - left) <= 0
                        return;

                    else{

                        int pivot = theArray[right];
                        int pivotLocation = partitionArray(left, right, pivot);
                        quickSort(left, pivotLocation - 1);
                        quickSort(pivotLocation + 1, right);
                    }
                }

                public int partitionArray(int left, int right, int pivot){

                    int leftPointer = left - 1;
                    int rightPointer = right;

                    while(true){

                        while(theArray[++leftPointer] < pivot)
                            ;

                        while(rightPointer > 0 && theArray[--rightPointer] > pivot)
                            ;

                        if(leftPointer >= rightPointer){
                            break;
                        } else {

                            swapValues(leftPointer, rightPointer)
                        }
                    }

                    swapValues(leftPointer, right);
                    return leftPointer;
                }

    # ----------------------------------------------------------- #