#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*

Big O Notation
    - Implementation independent
    - Platform independent

Linear Search
    - Best case is 1
    - Worst case is n
    - Average case is n/2

Binary Search
    - Case is log(base 2) of n

To claim: f(x) is O(g(x))
    - f(x) is time taken / work done by the algorithm or data structure, eg linked list search
    - g(x) is a function that puts a ceiling on the amount of work
    - |f(x)| <= c * g(x), where c is a constant

    |             /. = g(x) (always positive, cannot do negative work to sort an array)
    |            /.
    |           /.
    |          /.
    |         /.
    |        /.
    |       /.   -> dots cannot be above the line as the line is the MAX O(g(x)) so it can not be longer than it
    |      /.
    |     /.
    |    /.
    |   /.
    |  /.
    | /.
    |/____________________________________________


    - For example, Algorithm x's runtime is O(n)
    |             .           _/ -> this line is just the smallest function of n that puts an upper bound on x
    |                       _/
    |                     _/
    |           .       _/
    |                 _/
    |               _/
    |        .    _/
    |           _/
    |         _/
    |     . _/
    |     _/
    |  ._/
    | _/
    |/____________________________________________


    - For a big enough n, constants don't matter and the log functions always wins out
    - Easy Problems (Worst case)
        - O(log(base 2)n) = binary search
        - O(n) = linear search
        - O(nlogn) = general sorting problems
        - O(n^2) = direct convolution (when you reduce data, image processing, signals)
        - O(n^3) = matrix multiplication
        - O(2^n) = shortest route
        - O(n!) = permutations of a string
        - Constant = determining whether or not an array is sorted
        - Approximation = rendering images


Exercise 1: Identify the worst case time complexity of:

void multiply_accumulate(float input[N], float output[N]){
    for (int i = 0; i < N; i++){
        output[i] = 0
        for(int j = 0; j < N; j++){
            output[i] = output[i] + input[i] * input[j];
        }
    }
} -> output[N] = summation from j  of input[i]output[j]
    -> All cases are N^2

More efficient:
void multiply_accumulate(float input[N], float output[N]){
    float sum = 0.0;
    for (int j = 0; j < N; j++){
        sum += input[j];
    }
    for (int i = 0; i < N; i++){
        output[i] += input[i] * sum
    }
}
    -> All cases are now 2N


Exercise 2: Efficiency for sorting (Bubble sort):
for (int i = 0; i < N; i++){
    for (int j = 0; j < N- 1; j++){
        if arr[j] > arr[j + 1]{
            swap(arr[j], arr[j+1]);
        }
    }
}

    - Binary search with the price of sortign: O(N^2) + MO(log(base 2) N) = a big number
    - Quick sort has O(NlogN)
    - Insertion sort (inserting in the correct spot off the bat) = O(N/2) on average, O(N) worst case

Trees
                                            DATA
                                           /    \
                                        DATA    DATA
                                       /    \      \
                                      DATA  DATA   DATA

Exercise 3: Build a compound data type for a binary tree node that stores one float

typedef struct treeUno{
    float hello;
}TREE

TREE newTreeNode(){
    TREE h;
    struct treeUno *rightChild;
    struct treeUno *leftChild;
}









*/

int main(){


    return 0;
}