(Usage hints for this presentation)

Winter Term 2020/2021

Dr. Jens Lechtenbörger (License Information)

- Determine Big O complexity for following algorithms in Python!
- Hints
- This presentation embeds
klipse, to enable live
code execution.
- Thus, click into code on next slides, edit it, and have
results immediately displayed.
- If code does not execute, maybe reload without cache (Ctrl+F5 in Firefox)
- Based on in-browser implementation of Python (skulpt), not complete.

- Thus, click into code on next slides, edit it, and have
results immediately displayed.
- To determine Big O complexity, focus on the number of plus operations.
- Maybe introduce a new variable to count plus operations; output the final number.
- What patterns emerge?

- This presentation embeds
klipse, to enable live
code execution.

```
def naive_mult(op1, op2):
if op2 == 0: return 0
result = op1
while op2 > 1:
result += op1
op2 -= 1
return result
print(naive_mult(2, 3))
```

- Some notes
- Code on left is meant for non-negative integers
- Better code would test this

- Python basics
`def naive_mult(op1, op2)`

declares function`naive_mult`

with two operands`==`

tests for equality,`=`

is assignment to variable on left`result += op1`

is short for`result = result + op1`

- thus,
`op1`

is added to`result`

`-=`

similarly

- thus,

- Code on left is meant for non-negative integers

```
def naive_mult(op1, op2):
if op2 == 0: return 0
result = op1
while op2 > 1:
result += op1
op2 -= 1
return result
def naive_exp(op1, op2):
if op2 == 0: return 1
result = op1
while op2 > 1:
result = naive_mult(result, op1)
op2 -= 1
return result
print(naive_exp(2, 3))
```

- Some notes
`naive_mult`

is copied from previous slide`naive_exp`

shares same basic structure- But with invocation of
`naive_mult`

instead of plus operation

- But with invocation of

- What happens if the order of arguments to
`naive_mult`

on the previous slide is reversed, i.e., if`naive_mult(op1, result)`

instead of`naive_mult(result, op1)`

is executed?- Clearly, as multiplication is commutative, the result does not change.
- What about the resulting complexity?

Except where otherwise noted, the work “Complexity Example”, © 2019-2020 Jens Lechtenbörger, is published under the Creative Commons license CC BY-SA 4.0.

In particular, trademark rights are *not* licensed under this license.
Thus, rights concerning third party logos (e.g., on the title slide)
and other (trade-) marks (e.g., “Creative Commons” itself) remain with
their respective holders.