<jupyter_start><jupyter_text>Why Analyze Algorithm?* Procedure or formula for solving a problem* Some are so useful they have names:merge sort, bubble sort etc...* How can we compare the algos to know which is better<jupyter_code># Imagine I come up with a function...

def sum1(n):
    '''
    Take an input of n and return the sum of th numbers from 0 to n
    '''
    final_sum = 0
    for x in range(n+1):
        final_sum += x
    
    return final_sum 
sum1(5)
# And you came up with this function...

def sum2(n):
    '''
    Take an input of n and rturn the sum of the numbers from 0 to n
    '''
    return (n*(n+1))/2<jupyter_output><empty_output><jupyter_text>Function sum1 uses for loop to iteratively add across range 0 to nFunction sum2 uses formula to solve the problem  Objectively Compare Them* memory space* time to run<jupyter_code># built in magic commands in notebook
%timeit sum1(100)
# result in microseconds
%timeit sum2(100)
# result in nanoseconds<jupyter_output>238 ns ± 2.44 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)<jupyter_text>MICRO = `10^-6`NANO = `10^-9`Smaller number is obviously better* **Cannot simply rely on time to  run because all computers are different and some faster than others*** **To be hardware independent = Big O**  Big Oobjectively compare th efficinty of these two algorithm* compare the number of assignments each algorithm makesThe original `sum1` function will create an assignment `n+1` times, we can see this from the range based function. This means it will assign the `final_sum` variable n+1 times, We can say that for a problem of n size (in this case just a number n) this function will take `1+n` stepsThis `n` notation allows us to compare solutions and algorithm relative to the size of the problem, since `sum1(10)` and `sum1(1000000)` would take very different times to run but be using the same algorithm. We can note that as n grows very large, the +1 won't have much effect. So let's begin discussing how to build a syntax for this notation.Big-O notation dscribes **how quickly runtime will gro relative to the input as the input get arbitrarily large**  HOW WELL IT CAN SCALE as data increases?Remember, we want to **compare how quickly runtime will grow**, not compare exact runtime, since those can vary depending on hardwareSince we want to compare for a variety of input sizesm we are only concerned with the runtime grow relative to the input. This is why we use `n` for notation.As `n` gets arbitrarily large we only worry ablut terms that grow the fastest as `n` gets large, to this point, Big-O analysis is also known as **asymptotic analysis**.In maths, asymptotic analysis = **describing limiting behavior*** which part of the algorithm has the GREATEST effect on the final answer, which part of algo is the real bottleneck, which part is the limiting factor.As of the syntax sum1() can be said to be O(n) since its runtime grows linearly with the input size<jupyter_code>def Bigo(n):
    return 45*n**3 + 20*n**2 + 19
Bigo(1)
Bigo(2)
# starting to see that the 19 will not be a scaling or limiting factor
Bigo(10)<jupyter_output><empty_output><jupyter_text>* It can be seen that the `19` doesn't hold much weight anymore* The `20n**2` in this case is *2000** The `45n**3` in this case is *45,000* The part of the algo that really has a lot to do with the final answer as data scales, will not be the 45 but the n3. So this algo has an order of O(n**3)  Big-O complexity chart<jupyter_code>from math import log
import numpy as np
import matplotlib.pyplot as plt 
%matplotlib inline 
plt.style.use('bmh')

# Set up runtime comparisons
n = np.linspace(1, 10)
labels = ['Constant', 'Logarthmic', 'Linear', 'Log Linear', 'Quadratic', 'Cubic', 'Exponential']
big_o = [np.ones(n.shape), np.log(n), n, n*np.log(n), n**2, n**3, 2**n]

# Plot
plt.figure(figsize = (12,10))
plt.ylim(0,50)

for i in range(len(big_o)):
    plt.plot(n, big_o[i], label = labels[i])
    
plt.legend(loc = 0)
plt.ylabel('Relative Runtime')
plt.xlabel('n')<jupyter_output><empty_output><jupyter_text>Clearly we want to choose algorithm that stays away from any exponntial, quadratic, or cubic behavior!  Big-O Examples  O(1) Constant<jupyter_code>def func_constant(values):
    '''
    Prints first item in the list of values
    '''
    print (values[0])
    
func_constant([1,2,3])<jupyter_output>1<jupyter_text>It doesn't matter how large my values list becomes, the function/algo will only grab the indexed position `0` in that list  O(n^2) Quadratic<jupyter_code>def func_quad(lst):
    '''
    Prints pairs for every item in list
    '''
    for item_1 in lst:
        for item_2 in lst:
            print(item_1, item_2)
            
lst = [1, 2, 3]

func_quad(lst)<jupyter_output>1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3<jupyter_text>* two loops, one nested inside another* For a list of `n` items, we will have to perform `n` opreations for every item in the list! This means in total, we will perform `n` times `n` assignment, or `n^2`.So a list of `10` items have `100` operations. you can see how dengerous this can get for a large inputs! This is why Big-O is so important to be aware of!* hence, the input of `3` gives us `9` output iterations  Calculating Scale of Big-Oinsignificant terms drop out of Big-O notationWhen it comes to Big-O notation we only care about the most significant terms, remember as the input grows larger only the fastest growing term will matter.* Like taking limit towards Infinity<jupyter_code>def print_1(lst):
    '''
    Prints all items once
    '''
    for val in lst:
        print(val)
        
print_1(lst)

# can you see how this growth is linear to the input?
# O(n)
 def print_3(lst):
        '''
        Print all items three times
        '''
        for val in lst:
            print(val)
            
        for val in lst:
            print(val)
            
        for val in lst:
            print(val)

print_3(lst)<jupyter_output>1
2
3
1
2
3
1
2
3<jupyter_text>This algo will run `3` times for each `n`, so this becomes an order of `3(n)`. It is still linear.More importantly, `1(infinity)` is not really differnt than `(infinity)` and We can drop insignificant constants.So this too is `O(n)`<jupyter_code>def comp(lst):
    '''
    This function prints the first item O(1) it is a constant
    Then it prints the first 1/2 of the list O(n/2)
    Then prints a string 10 times O(10) ti is a constant
    '''
    print(lst[0])
    
    midpoint = len(lst)//2
    
    for val in lst[:midpoint]:
        print(val)
        
    for x in range(10):
        print('number')
lst = [1,2,3,4,5,6,7,8,9,10]
comp(lst)<jupyter_output>1
1
2
3
4
5
number
number
number
number
number
number
number
number
number
number<jupyter_text>O(1 + n/2 + 10)As `n` gets larger and larger (scales up) you can see rasily how the `1` and the `10` quickly begin to mean nothing.And the `//2` will begin to hav no effect eitherEnd up with `O(n)`  Worst Case vs Best CaseMany times we are only concerned with the worst possible case of the algorithm, but in an interview setting its is important to keep in mind that worst case and best caes scenarios may be completely different Big-O times<jupyter_code>def matcher(lst, match):
    '''
    Given a list lst, return a boolean indicating if match item is in the list
    '''
    for item in lst:
        if item == match:
            return True
    return False
lst
matcher(lst, 1) # this is best case because item seeked is index 0, O(1) Best case becoms a constant
matcher(lst, 20) # worst case, entire list must be searched, n element, O(n) Worst case becomes linear<jupyter_output><empty_output><jupyter_text>Space ComplexityAlso concerned with how much memory/space an algorithm uses. The notation of space complexity is the same, but instead of checking the time of operations, we check the size of the allocation of memory<jupyter_code>def memory(n = 10):
    '''
    Prints "Memory!" n times
    '''
    for x in range(n): # TIME COMPLEXITY O(n)
        print('Memory!') # SPACE COMPLEXITY O(1)

memory(10)<jupyter_output>Memory!
Memory!
Memory!
Memory!
Memory!
Memory!
Memory!
Memory!
Memory!
Memory!
{'fraction_non_alphanumeric': 0.08515069835824553, 'fraction_numerical': 0.025851506983582455, 'mean_word_length': 3.7184971098265898, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '610661', 'license': 'CC0-1.0', 'n_tokens_mistral': 2647, 'n_tokens_neox': 2509, 'n_words': 1179, 'path': 'Python/algorithms.ipynb', 'repo_name': 'VishwasSaini32/Data-Science', 'size': '8162'}