IMG_5418.jpeg

# Algorithmic Complexity ## What is Complexity? * Algorithmic complexity is a measure of how much time (Time Complexity) and space (Space Complexity) is needed to execute an algorithm. * Complexity is a function of the input size $$ Complexity = f(input\ size) $$ ### Why is it Needed? * Hel...

# Algorithmic Complexity ## What is Complexity? * Algorithmic complexity is a measure of how much time (Time Complexity) and space (Space Complexity) is needed to execute an algorithm. * Complexity is a function of the input size $$ Complexity = f(input\ size) $$ ### Why is it Needed? * Helps compare efficiency of algorithms * Estimate resources to run large problems ## Time Complexity * Time complexity refers to the amount of time taken by an algorithm to run as a function of the length of the input. ### How to Measure Time Complexity 1. **Experimental Analysis:** * Implement algorithm * Run with inputs of varying size * Get actual running time * Plot the data \* _Not usually done because it is affected by hardware/software, and requires implementation_ 2. **Theoretical Analysis** * Determine the number of elementary operations as a function of input size * Ignores hardware/software * Allows comparison of algorithms ### Elementary Operations * Assigning a value to a variable * Calling a function * Performing an arithmetic operation * Comparing two numbers * Accessing an array element * Returning from a function ### Counting Instructions ```python def sum(a, b): # count c = a + b # 1 return c # 1 # Total: 3 ``` ```python def sum(A): total = 0 # 1 for a in A: # n + 1 total += a # n return total # 1 # Total: 2n + 3 ``` ## Asymptotic Analysis * Goal: Estimate rate of growth as input size increases * Using elementary operations is still too tedious * Asymptotic analysis simplifies by: * Ignoring constants * Focusing on the dominant terms * Big-O notation is used ### Common Growth Functions | Complexity | Name | | :------------------ | :------------ | | $O(1)$ | Constant | | $O(log\ n)$ | Logarithmic | | $O(n)$ | Linear | | $O(n\ log\ n)$ | Log-Linear | | $O(n^2)$ | Quadratic | | $O(n^3)$ | Cubic | | $O(2^n)$ | Exponential | | $O(n!)$ | Factorial | ## Big-O Notation ### Definition $f(n) = O(g(n))$ if and only if there exists positive constants c and n such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$ ### Graphical Representation * A graph shows $f(n)$ growing slower than $g(n)$ after point $n_0$ ### Examples #### Example 1 $$ f(n) = 3n^2 + 5n + 10 $$ $$ f(n) = O(n^2) $$ * Constants are dropped * Lower order terms are dropped #### Example 2 ```python for i in range(n): print(i) ``` $O(n)$ #### Example 3 ```python for i in range(n): for j in range(n): print(i, j) ``` $O(n^2)$ #### Example 4 ```python i = 1 while i < n: i *= 2 ``` $O(log\ n)$ ## Space Complexity * Space complexity refers to the amount of memory space taken by an algorithm to run as a function of the length of the input. * Includes space for input data and auxiliary space $$ space\ complexity = Auxiliary\ Space + Input\ Space $$ * Auxiliary space is the extra space used by the algorithm ### Example 1 ```python def sum(a, b): c = a + b return c ``` $O(1)$ ### Example 2 ```python def sum(A): total = 0 for a in A: total += a return total ``` $O(1)$ ### Example 3 ```python def copy(A): B = * len(A) for i in range(len(A)): B[i] = A[i] return B ``` $O(n)$