<jupyter_start><jupyter_text>Introduction  **What?** Time and space complexity  What constitute an efficient algorithm?  - Algorithm’s efficiency measures both the time and space (memory) it takes when executed.- The **best algorithm** = least amount of time + least amount of space. - **Rreality** is that algorithms have a **tradeoff** between saving space or time.- Admiting there is ia tradeoff means that:    - The best algorithm **depends** on our requirements.    - If need both least time and memory we can settle for the average.  Space complexity  - Space complexity of an algorithm is the amount of space it uses for execution in relation to the size of the input. The keyword here is **in relation to the iput size**.- Assume that adding a single integer to the list takes `c` amout of space and other initial operations, including creating a new list, takes `d` amount space. Then the space taken can be computed as: `c*n+d` where `n` is our input size. - The values of the **constants** `c` and `d` are outside of the control of the algorithm and depend on factors such as programming language, hardware specifications, etc.    - `when n       -> c*n + d`    - `when n = 10  -> c*10 + d`    - `when n = 100 -> c*100 + d`<jupyter_code>n = int(input())

nums = []
for i in range(1, n+1):
    nums.append(i*i)
print(nums)<jupyter_output>100
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249, 3364, 3481, 3600, 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 5041, 5184, 5329, 5476, 5625, 5776, 5929, 6084, 6241, 6400, 6561, 6724, 6889, 7056, 7225, 7396, 7569, 7744, 7921, 8100, 8281, 8464, 8649, 8836, 9025, 9216, 9409, 9604, 9801, 10000]<jupyter_text>Time complexity  - Time complexity is the number of elementary operations an algorithm performs in relation to the input size. Here, we count the number of operations, instead of time itself, based on the assumption that each operation takes a fixed amount of time to complete. - The algorithm performs `n` number of operations (n iterations of the loop) to complete its execution.- As we did earlier the equation for the time complexity is still: `c*n + d` thus the time complexity of this algorithm is also in the order of `n`.<jupyter_code>n = int(input())

nums = []
for i in range(1, n+1):
    nums.append(i*i)
print(nums)<jupyter_output>10
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]<jupyter_text>Asymptotic analysis   - Do we need the exact value of the equation? No, we don't! Instead, we use the highest order of the variable `n` as a representative of the space complexity.- This type of analysis is called **asymptotic analysis** and it evaluates how the performance changes as the input size increases. - In conclusion:    - `c*n + d` has an order of `n` space complexity.    - `c*n^2 + d*n + e` has an order of `n^2` space complexity.  Best, Worst, and Average Cases  - However asymptotic analysis is not all about worst case scenatio. - **Usually**, we consider three cases when analyzing an algorithm: best, worst, and average.- Scenarios:    - `k` is stored in the 0th index, just need one interation.    - `k` is NOT stored in the list, it takes `n+1` iterations- In linear search, the number of iterations the algorithm takes to complete execution follows this pattern.    - `When k is stored at the 0th index  -> 1 iteration`    - `When k is stored at the 1st index  -> 2 iterations`    - `When k is stored at the 2nd index  -> 3 iterations`    - `When k is stored at the 3rd index  -> 4 iterations`    - `:                                  :`    - `When k is stored at the nth index  -> n iterations`    - `When k is not in the list          -> n+1 iterations`- This can computed with this formula: ![image.png](attachment:image.png)<jupyter_code>def linear_search(nums, n, k):
    """
    Linear search algorithm: a simple for 
    loop to search if a given integer k is present 
    in a list named nums of size n.
    """
    
    for i in range(n):
        if k == nums[i]:            
            return i
    return -1

import numpy as np
print("List being probed", list(np.arange(1,7,1)))
print("Best case scenario, index found at", linear_search(list(np.arange(1,7,1)), 6, 1))
print("Worst case scenario, index found at", linear_search(list(np.arange(1,7,1)), 6, 7))<jupyter_output>List being probed [1, 2, 3, 4, 5, 6]
Best case scenario, index found at 0
Worst case scenario, index found at -1
{'fraction_non_alphanumeric': 0.10342598577892695, 'fraction_numerical': 0.09265244559362207, 'mean_word_length': 3.5554465161923456, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '421783', 'license': 'OLDAP-2.3', 'n_tokens_mistral': 1786, 'n_tokens_neox': 1418, 'n_words': 697, 'path': '___Algorithms/Time and space complexity.ipynb', 'repo_name': 'kyaiooiayk/Python-Programming', 'size': '4641'}