<jupyter_start><jupyter_text>Examples of Algorithm Analysis Using Big-Oh  What Are We Doing?* Characterizing the running times of algorithms using Big-Oh notation* Over the next few notebooks we'll be doing an example for each of the seven fundamental functions we discussed in the last notebook.* We'll be demonstrating three different techniques to perform Big-Oh analysis where each subsequent technique will use less explicit or formal justification, so the analysis will get faster with each subsequent technique.  * Three Techniques for Performing Big-Oh Analysis:  * Use the definition of Big-Oh on the calculated running time   * Use Big-Oh rules on the calculated running time  * Identify the line(s) responsible for the largest growth rateNote (1): Using these three different techniques allows us to see how all of the topics we have covered so far come into play as well as being able to see why we're able to ignore particular steps and details if we just want to be able to quickly come to an answer.Note (2): In these examples we'll be analyzing Python implementations of algorithms as opposed to the previously discussed pseudocode.  Steps for Performing Big-Oh Analysis  1. Identify each primitive operation in the code block  2. Count how many times each primitive operation is executed    3. Calculate the running time by summing the counts of primitive operations    4. Perform a Big-Oh analysis on the computed running time Note (3): When counting primitive operations we'll ignore the line beginning with the keyword $def$ which serves as the function’s signature since we care about the running time of the function's body.Note (4): Remember we're assuming all primitive operations will have the same constant execution time which allows us to simply count how many times each primitive operation executes and sum up the resulting counts.Note (5): Also remember if we know a finite number of primitive operations are executing but we can't count the exact amount since the implementation details are being abstracted away (like in Python for loops), then we'll use constant variables to represent the number of executed primitive operations for that line of code.    Note (6): This approach of using constant variables will still allow us to use Big-Oh analysis to correctly identify the growth rate since Big-Oh allows us to ignore lower-order terms and constant factors.  Constant Time Example<jupyter_code>a = 0
b = 1

result = a + b<jupyter_output><empty_output><jupyter_text>* $\color{blue}{a = 0}$, is $\color{blue}{1}$ operation since we're assigning a value of $0$ to the variable $a$.* $\color{blue}{b = 1}$, is also $\color{blue}{1}$ operation since we're assigning a value of $1$ to the variable $b$.* $\color{blue}{result = a + b}$, is $\color{blue}{2}$ operations since we're performing an arithmetic operation and assigning the computation to the variable result. Therefore, the total running time of the algorithm is:$$t = \color{blue}{1 + 1 + 2} = 4$$. Using the Definition of Big-Oh on the Calculated Running Time* If you remember the definition of Big-Oh is the following:  Let $f(n)$ and $g(n)$ be functions mapping positive integers to positive real numbers.  We say $f(n)$ $\epsilon$ $O(g(n))$ if there is a real constant $c > 0$ and an integer constant $n_0 \geq 1$ such that  $f(n) \leq cg(n)$, for all $n \geq n_0$.  So, we need to determine a real constant $c > 0$ and an integer constant $n_0 \geq 1$ such that $f(n) \leq cg(n)$ for all $n \geq n_0$.  Here, $f(n) = t = 4$.  If we let $c = 5$, then   $4 \leq 5g(n)$ for all $n \geq n_0$.  If we let $g(n) = 1$, then  $4 \leq 5(1)$ for all $n \geq n_0$.  If we let $n_0 = 1$, then  $4 \leq 5$ for all $n \geq 1$.  Therefore, $t = 4$ is $O(1)$.  Note (7): Our choice for $c$ and $n_0$ are one of infinitely many choices that can demonstrate $f(n)$ is $O(g(n))$, e.g., we could have chosen $c = 10$ and $n_0 = 2$. Using Big-Oh Rules on the Calculated Running Time* Instead of going through the long-winded process of using the definition we can use some Big-Oh rules to perform the analysis.* We'll be using the following two rules:  * **Use the smallest/closet possible class of functions**, e.g., $f(n) = 7n$ is $O(n)$ instead of $f(n) = 7n$ is $O(n^3)$.  * **Use the simplest expression of the class of function**, e.g., $f(n) = 6n^2 + 5n + 8$ is $O(n^2)$ instead of $f(n) = 6n^2 + 5n + 8$ is $O(6n^2)$.* Here, we have $t = 4$, so the smallest/closest possible class of function and the simplest expression of the determined class of function that can characterize the behavior of $t$ is $O(1)$. Identifying the Line(s) Responsible for the Largest Growth Rate * Using this technique we won't even need to calculate the running time $t$.* We can just look at the code and recognize that all of the lines consist of primitive operations that are executed one time, so the running time in terms of Big-Oh is $O(1)$.  Logarithmic Time Example * In a future notebook we'll be analyzing the binary search algorithm.  * We're delaying the analysis because it will be beneficial to first go over what binary search does, how it works, and the visualization of some examples.    Linear Time Example<jupyter_code># Return the product of the elements in the list A of length n.
def calculateProduct(A):
    product = 1
    for i in A:
        product *= i
    return product<jupyter_output><empty_output><jupyter_text>* $\color{blue}{product = 1}$, is $\color{blue}{1}$ operation since we're assigning a value of $1$ to the variable $product$.* $\color{blue}{for}$ $\color{blue}{i}$ $\color{blue}{in}$ $\color{blue}{A}$$\color{blue}{:}$, is $\color{blue}{c_1 + c_2n}$ operations where if you remember $c_1$ represents the constant number of primitive operations associated with the initializing and the terminating of the for loop, and $c_2$ represents the number of primitive operations associated with the maintenance of the iterator which is done $n$ times.* $\color{blue}{product}$ $\color{blue}{*= i}$, is $\color{blue}{2n}$ operations since we're performing an arithmetic operation and assigning the result to the variable $product$ during each iteration of the loop. * $\color{blue}{return}$ $\color{blue}{product}$, is $\color{blue}{1}$ operation since we're returning the variable $product$ from the function.Therefore, the total running time of the algorithm is:$$t = \color{blue}{1 + c_1 + c_2n + 2n + 1} = 2 + c_1 + c_2n + 2n$$. Using the Definition of Big-Oh on the Calculated Running Time* We need to determine a real constant $c > 0$ and an integer constant $n_0 \geq 1$ such that $f(n) \leq cg(n)$ for all $n \geq n_0$.  Here, $f(n) = t = 2 + c_1 + c_2n + 2n$.  If we let $c = 2 + c_1 + c_2 + 2$, then   $2 + c_1 + c_2n + 2n \leq (2 + c_1 + c_2 + 2)g(n)$ for all $n \geq n_0$.  If we let $g(n) = n$, then  $2 + c_1 + c_2n + 2n \leq (2 + c_1 + c_2 + 2)n$ for all $n \geq n_0$.  If we let $n_0 = 1$, then  $2 + c_1 + c_2n + 2n \leq (2 + c_1 + c_2 + 2)n$ for all $n \geq 1$.  Therefore, $t = 2 + c_1 + c_2n + 2n$ is $O(n)$. Using Big-Oh Rules on the Calculated Running Time* We'll be using the two rules we used in the previous example.* Here, we have $t = 2 + c_1 + c_2n + 2n$, so the smallest/closest possible class of function and the simplest expression of the determined class of function that can characterize the behavior of $t$ is $O(n)$. Identifying the Line(s) Responsible for the Largest Growth Rate * Once again using this technique means we won't even need to calculate the running time $t$. We can just look at the code and recognize that the for loop consists of $n$ iterations, so it will cause the running time in terms of Big-Oh to be $O(n)$.  N-Log-N Time Example * We'll be analyzing the merge sort algorithm in a future notebook for the same reasons as the logarithmic time example.    Quadratic Time Example<jupyter_code># Determine if the intersection of the three sequences of numbers, A, B, and C is empty.
# In other words determine if there is no element x such that x belongs to A, B, and C.
# We'll assume each list has a length of n and that no individual sequence contains 
# duplicate values, but there may be numbers that are in two or three of the sequences
# E.g., A = [1, 2, 3], B = [1, 2, 4], C = [1, 5, 6] is fine since no individual sequence 
# has duplicate values, but A = [1, 2, 2], B = [2, 3, 4], and C = [2, 4, 5] is not fine 
# since 2 is a duplicated value in A.
def threeWaySetDisjointness(A, B, C):
    for a in A:
        for b in B:
            if a == b:
                for c in C:
                    if a == c:
                        return False
    return True<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.094472710453284, 'fraction_numerical': 0.018270120259019425, 'mean_word_length': 3.8975084937712343, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 16, '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': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '645382', 'license': 'MIT', 'n_tokens_mistral': 2582, 'n_tokens_neox': 2434, 'n_words': 1363, 'path': '04-Algorithm_Analysis_Examples(Constant_Linear_Quadratic).ipynb', 'repo_name': 'jchiarulli/data_structures_and_algorithms', 'size': '8648'}