Computational Complexity

Question 1

Understand efficiency of programs

Answer 1

Separate time and space efficiency of a program

Question 2

Challenges

Answer 2

• a program can be implemented in many different ways
• solve a problem using only a handful of different algorithms
• separate choices of implementation from abstract algorithms

Question 3

Evaluate efficiency

Answer 3

• use a timer
• count operations
• abstract notion of order of growth

Question 4

Timing a program

Answer 4

1. start clock
2. call function
3. stop clock

Question 5

Timing programs is inconsistent

Answer 5

GOAL to evaluate diff. algorithms

Question 6

Running time

-(time varies for different inputs, but cannot really express a relationship between inputs and time!)

Answer 6

+ varies between algorithms

• varies between implementations
• varies between computers
• not predictable based on small inputs

Question 7

Which operations to count

Answer 7

Assumes steps take constant time

• mathematical operation
• comparisons
• assignments
• accessing objects in memory

Question 8

Counting operations, better but…

Answer 8

GOAL to evaluate different algorithms

Question 9

Counting operations

+(count varies for diff. inputs and can come up with a relationship between inputs and the count)

Answer 9

+ depends on algorithm
- depends on implementation
- independent of computers
+ no real def. of which operations to count

Question 10

Needs a better way

what we HAVE

Answer 10

• timing and counting evaluate implementations

* timing evaluates machines

Question 11

what we WANT

Answer 11

• evaluate algorithm
• evaluate scalability
• evaluate in terms of input size

Question 12

Need to which input to use

Answer 12

• efficiency in terms of input
• could be an integer
• could be length of list
• you decide

Question 13

Different inputs

Answer 13

• first element in a list -> BEST CASE
• not in list -> WORST CASE
• look through half -> AVG CASE

Question 14

Best case

Answer 14

min. running time
- constant
- first element of any list

Question 15

Average case

Answer 15

avg. running time

- practical measure

Question 16

Worst case

Answer 16

max. running time
- linear in length of list
- must search entire list

Question 17

Orders of Growth - goal

Answer 17

• input is very big
• growth of program’s run time
• upper bound
• do not need to be precise “order of” not “exact”
• largest factor

Question 18

Input is very big

Answer 18

Want to evaluate programs efficiency when input is very big

Question 19

Growth of program’s run time

Answer 19

Want to express program’s run time as input grows

Question 20

Upper bound

Answer 20

Want to put an upper bound on growth

Question 21

“order of” not “exact”

Answer 21

Do not need to be precise “order of” not “exact” growth

Question 22

Largest factor

Answer 22

We will look at largest factor in run time

Question 23

Types of orders of growth

Answer 23

- constant
\+ linear
- quadratic
- logarithmic
\+ n log n
- exponential

Question 24

Measuring Order of Growth

Answer 24

Big Oh Notation

Question 25

Big Oh Notation

Answer 25

Measures - upper bound on the asymptotic growth - is used to describe worst case

Question 26

Worst Case

Answer 26

- Occurs often - Is the bottleneck - Express rate of growth is relative to input size - Evaluate algorithm not machine or implementation

Question 27

Worst case asymptotic complexity

Answer 27

- ignore additive constants | - ignore multiplicative constants

Question 28

Simplification

Answer 28

- drop constants - drop multiplicative factors + focus on dominant terms

Question 29

Examples

Answer 29

``` O(n^2) -> n^2 + 2^n + 2 O(n^2) -> n^2 + 100000n + 3^1000 O(n) -> log(n) + n + 4 O(n log n) -> 0.0001*n*log(n) + 300n O(3^n) -> 2^n30 + 3^n ```

Question 30

complexity | ordered low to high

Answer 30

O(1) -> O(log n) -> O(n) -> | O(n log n) -> O(n^C) -> O(C^n)

Question 31

Analyse programs and their complexity

Answer 31

- Combine complexity classes | - Law of addition for O()

Question 32

Combine complexity classes

Answer 32

- analyse statements inside functions | - apply some rules, focus on dominant term

Question 33

Law of addition for O()

Answer 33

- Used with sequential statements - O(f(n)) + O(g(n)) is O(f(n) + g(n)) - O(n) + O(n*n) = O(n+n^2) = O(n^2)

Question 34

O(1)

Answer 34

denotes constant running time

Question 35

O(log n)

Answer 35

denotes logarithmic running time

Question 36

O(n)

Answer 36

denotes linear running time

Question 37

O(n^C)

Answer 37

denotes polynomial running time (c is constant)

Question 38

O(C^n)

Answer 38

denotes exponential running time (c is a constant being raised to a power based on size of input)

Question 39

Constant Complexity

Answer 39

- independent of inputs - very few interesting algorithms in this class - can have loops or recursive calls

Question 40

Logarithmic Complexity

Answer 40

- Grows as log of size of one of its inputs - examples: - bisection search - binary search of a list

Question 41

Linear Complexity

Answer 41

- Searching a list in sequence to see if an element is present - add char to a string

Question 42

Linear recursive complexity

Answer 42

- complexity can depend on number of recursive calls - number of times around the loop is n - number of operations inside loop is a constant

Question 43

Log-Linear complexity

Answer 43

- many practical algorithms are log-linear | - like the merge sort

Question 44

Polynomial Complexity

Answer 44

- most are quadratic n^2 - commonly for - nested loops - recursive functions calls

Question 45

o() for nested loops | (see file "example-analysing-complexity.py" in week-6.

Answer 45

- computes n^2 very inefficiently - look at the ranges - nested loops, each iterating n times

Question 46

When input is a list

Answer 46

Must define what size of input means - previously it was the magnitude of a number - here it is the length of list

Question 47

Common Python functions | List

Answer 47

index, store, length append => O(1) ==, remove, copy, reverse, iteration, in list => O(n)

Question 48

Common Python functions | Dictionaries

Answer 48

Worst Case: index, store, length, delete, iteration => O(n) Avg case is however often O(1)

Question 49

Big Oh summary | compare efficiency of algortihms

Answer 49

- notation that describes growth - lower order of growth is better - independent of machine or specific implementation

Question 50

Big Oh summary | use Big Oh

Answer 50

- describe order of growth - asymptotic notation - upper bound - worst case analysis

Question 51

Notes on Big Oh

Answer 51

https://prod-edxapp.edx-cdn.org/assets/courseware/v1/b874db7cc14e722ce7b921d11d944026/asset-v1:MITx+6.00.1x+2T2019+type@asset+block/handouts_Big_O.pdf