<jupyter_start><jupyter_text>Introduction to Algorithm Analysis and Big OIn this lesson we will discuss how to analyze Algorithms and why it is important to do so!  Why analyze algorithms?Before we begin, let's clarify what an algorithm is. In this course, an **algorithm** is simply a procedure or formula for solving a problem. Some problems are famous enougth that the algortihms have names, as well as some procedures being common enough that the algorithm associated with it also has a name. So now we have a good question we need to answer: How to analilyze algorithms and how can we compare algorithms against each others?Imagine if you and a friend came up with functions to some functions from 0 no N. How whould you compare the functions and algorithms whitin the functions? Let's say you both came up with these separate functions:<jupyter_code># First function
def sum1(n):
    """
    Take a input of N and return the sum of the numbers from 0 to N.
    """
    final_sum = 0
    for i in range(n + 1):
        final_sum += i

    return final_sum
sum1(10)
def sum2(n):
    """
    Take a input of N and return the sum of the numbers from 0 to N
    """
    return n*(n+1) // 2
sum2(10)<jupyter_output><empty_output><jupyter_text>You will notice both the functions have same result, but completely diferent algorithms. You'll note that the first function iteratively adds the numbers, while the second functions make use of:$$\sum_{i=0}^{n} {i} = \frac{n(n+1)}{2}$$So how can we objectively compare the algorithms? We could compare the amount of space they take in memory or we could also compare how much time it takes each function to run. We can use the built in **%timeit** magic function in jupyter to compare the time of the functions. The [**%timeit**](https://ipython.org/ipython-doc/3/interactive/magics.htmlmagic-timeit) magic in the jupyter notebooks will repeat the loop iteration a certain number of times and takes the best result. Check out the link for the documentation.Let's go ahead and compare the time it took to run the functions:<jupyter_code>%timeit sum1(10)
%timeit sum2(10)<jupyter_output>169 ns ± 0.44 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
{'fraction_non_alphanumeric': 0.0658193372673627, 'fraction_numerical': 0.018157058556513846, 'mean_word_length': 4.247619047619048, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 8, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '646684', 'license': 'MIT', 'n_tokens_mistral': 632, 'n_tokens_neox': 592, 'n_words': 334, 'path': 'jupyter/1-introduction-big-O-notation.ipynb', 'repo_name': 'rafaelcassau/algorithms', 'size': '2203'}