<jupyter_start><jupyter_text>Big-O DemoHere's a little code demo that may help reinforce Big-O.We're seeking to quantify an order of magnitude when describing run time performance. If two competing algorithms operating on big complex problems finish within a few seconds or microseconds of each other, then we'd say they both have the same run time performance (Big-O). What we're talking about is: one algorithm takes seconds or minutes, and the other takes days or longer.The code below reads an integer (`n`) from the user and creates two processes. In one process, the product of `n` * `n` is calculated through straight multiplication. In the other process, the product of `n` * `n` is calculated in a loop using repeated addition. They both come up with the same answer, so which one is better? The answer depends on how big `n` is.There are a few important notes about this little demo:1. There's no exception handling for the input, so it's easy to crash it.2. The processes are synchronized so they both start their calculations at the same time, within a few microseconds :-). The program also implements a thread lock to ensure both processes don't try to write to `stdout` at the same time. This thread locking has no impact on the elapsed time calculations that get displayed and should not influence the results. The elapsed time display is in the form: `H:MM:SS.Micro Seconds`.3. You should notice that for small-ish integer inputs (let's say up to about `100000`), the processes run in nearly the same amount of time (addition may actually be faster in some cases). Multiplication in a microprocessor is more complex than addition. As Computer Scientists like to say: it's *expensive*. Assuming that multiplication is one step (as discussed in the class notes), we would classify the process using multiplication as running in constant time `O(1)` and the process using addition as running in `O(n)` time. No matter how big the input is, multiplication always finishes in roughly the same time (even if it may lose to repeated addition for smaller inputs); however as the size of the input grows, the run time performance of repeated addition gets much worse (grows linearly), because it's proportional to the size of the input.Run the code a few times with different inputs and see what happens. What if you enter `1`?  How about `1000`?  How about `10000`?  Try 1 followed by 8 zeros. On my machine that took the multiplication process about .03 seconds and the addition process about 3.5 seconds. Where's the crossover when multiplication runs in less time than repeated addition?  What if you try a really, really big input and let it run overnight?*Performance depends on the speed of the computer running this code, scheduler loading, available memory, etc.*<jupyter_code>#! /usr/bin/env python3

from multiprocessing import Barrier, Lock, Process
from datetime import datetime

# ---------------------------------------------


def cleanTime(t):
    hh = t.hour
    mm = t.minute
    ss = t.second
    us = t.microsecond
    return f'{hh:02d}:{mm:02d}:{ss:02d}:{us}'

# ---------------------------------------------


def startClock(mode, start):
    print(f'{cleanTime(start)} start process using {mode}')
    print('---------------------------------------------------')

# ---------------------------------------------


def stopClock(mode, result, start, stop):
    print(f'{cleanTime(stop)} finish process using {mode}')
    print(f'n squared = {result}')
    print(f'Elapsed time = {str(stop-start)}')
    print('---------------------------------------------------')

# ---------------------------------------------


def Addition(barrier, lock, n):
    start = datetime.now()
    with lock:
        startClock('Addition', start)
    barrier.wait()

   # Calculate n^2 using addition
    squared = 0
    for i in range(n):
        squared += n

    stop = datetime.now()
    with lock:
        stopClock('Addition', squared, start, stop)

# ---------------------------------------------


def Multiplication(barrier, lock, n):
    start = datetime.now()
    with lock:
        startClock('Multiplication', start)
    barrier.wait()

    # Calculate n^2 using multiplication
    squared = n*n

    stop = datetime.now()
    with lock:
        stopClock('Multiplication', squared, start, stop)

# ---------------------------------------------


def main():
    barrier = Barrier(2)
    lock = Lock()
    n = int(input("Enter an integer: "))
    print()
    Process(target=Addition, args=(barrier, lock, n)).start()
    Process(target=Multiplication, args=(barrier, lock, n)).start()

# ---------------------------------------------


if __name__ == '__main__':
    main()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1633171144489105, 'fraction_numerical': 0.007827374656230167, 'mean_word_length': 2.6736596736596736, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, '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': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '555510', 'license': 'MIT', 'n_tokens_mistral': 1215, 'n_tokens_neox': 1134, 'n_words': 583, 'path': 'content/13_bigo.ipynb', 'repo_name': 'geozeke/notebooks', 'size': '4727'}