<jupyter_start><jupyter_text>*Please execute the cell below before answering any questions. If you do not, the required support code will not be loaded and you may experience exceptions. If you forget, just come back and run the import cell then retry your answer.*<jupyter_code>from lesson1 import main<jupyter_output><empty_output><jupyter_text>Lesson 1 - Big O NotationBig O is a way to discuss the growth of functions by describing the time efficiency of those functions. In other words, as the algorithm has to process more information, what happens to the time it takes to process that information. As we discuss time in Big O we really mean "relative" time. An algorithm's Big O does not change from computing device to computing device. The algorithm will run faster on modern hardware than it does on older hardware but compared to other algorithms that solve the same problem it's time efficiency stays relatively the same as compared to those other algorithms.  Let's look at a simple example:<jupyter_code># Given the following function, indicate what you think the Big O is based on the information given so far
def do_summation(input):
    sum = 0
    for x in input:
        sum += x
    return sum

# Possible answers
a = "O(n^2)"
b = "O(1)"
c = "O(n)"
my_answer = None # change my_answer to match the letter you choose
main.q1(my_answer)<jupyter_output><empty_output><jupyter_text>The correct answer to the question above is (c). The reason for this is that the time of the function increases relative to the size of the input. O(n) is how we represent an algorithm whose time efficiency is directly correlated to the size of the data being processed. O(1) represents a constant time algorithm. In other words, if the size of the input increases or decreases there is no change in how long the algorithm takes to complete. We will see an example of that shortly. When we see O(n2) that means the function's execution time is relative to the square of the size of input. An input of size 8 will take approximately 16 times longer to execute than an input of size 2 and so on.  Let's now consider a function with a constant time efficiency.<jupyter_code>def get_element(input, index):
    return input[index]<jupyter_output><empty_output><jupyter_text>The function above has constant time, O(1), because there is no looping. By providing an index, the exact element is found immediately, regardless of how many items are in the input.  When dealing with multiple loops, Big O is determined either as a sum or as a product. If the loops appear one after the other, then the sum of the Big O for the individual loops is used to describe the Big O for the algorithm. On the other hand, if the loops are nested, then the Big O for the algorithm is the product of the Big O for the individual loops.<jupyter_code># Given the following function, indicate what you think the Big O is 
def do_pairwise_summation(input):
    sum = 0
    for x in input:
        for y in input:
            sum += x + y
    return sum

# Possible answers
a = "O(n^2)"
b = "O(1)"
c = "O(n)"
my_answer = None # change my_answer to match the letter you choose
main.q2(my_answer)
# Given the following function, indicate what you think the Big O is 
def do_summation(input1, input2):
    sum = 0
    for x in input:
        sum += x
    for y in input:
        sum += y
    return sum

# Possible answers
a = "O(n^2)"
b = "O(1)"
c = "O(m + n)"
my_answer = None # change my_answer to match the letter you choose
main.q3(my_answer)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.05532034998588767, 'fraction_numerical': 0.006491673722833756, 'mean_word_length': 4.055634807417975, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 17, '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': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '459496', 'license': 'MIT', 'n_tokens_mistral': 964, 'n_tokens_neox': 943, 'n_words': 550, 'path': 'Lesson 1 - Big O Notation.ipynb', 'repo_name': 'jimv3/csp', 'size': '3543'}