(Usage hints for this presentation)

October 2019

Dr. Jens Lechtenbörger (License Information)

- Determine the Big O complexity for the following algorithms in Python!
- Hints
- This presentation embeds
klipse, to enable live
code execution.
- Thus, click into code, edit it, and have results immediately
displayed.
- Based on in-browser implementation of Python (skulpt), not complete.

- Thus, click into code, 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:
print("Not supported")
return 42
if op2 == 0: return 0
result = op1
while op2 > 1:
result += op1
op2 -= 1
return result
print(naive_mult(2, 3))
```

```
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))
```

- 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 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.