(Usage hints for this presentation)

Winter Term 2023/2024

Dr. Jens Lechtenbörger (License Information)

- Determine Big O complexity for following algorithms in Python!
- Background

- Figure out what the algorithms on the next slides do.
- If you are not sure, maybe copy&paste into Python Tutor, which enables step-by-step execution with visualizations of values.

- Determine the algorithms’ complexities in terms of numbers of
necessary plus operations.
- If you are puzzled about the focus on plus operations, note
that they occur at the inner-most level of nesting in
`while`

loops. For each iteration of a loop, a fixed number of other operations is executed, and those are covered by a constant factor in the definition of Big O complexity (\(M\) at Wikipedia.)

- If you are puzzled about the focus on plus operations, note
that they occur at the inner-most level of nesting in

Subsequent quizzes lead to solutions. Please try yourself first.

```
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,
`return`

exits the function, delivers result

- 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 was reversed, i.e., if`naive_mult(op1, result)`

instead of`naive_mult(result, op1)`

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

Source files are available on GitLab (check out embedded submodules) under free licenses. Icons of custom controls are by @fontawesome, released under CC BY 4.0.

Except where otherwise noted, the work “Complexity Example”, © 2019-2022 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.