# Complexity Example

(Usage hints for this presentation)

July 2020

DBIS Group Prof. Dr. Gottfried Vossen
Chair for Computer Science
Dept. of Information Systems
WWU Münster, Germany

## Sample Algorithms

• 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.
• Based on in-browser implementation of Python (skulpt), not complete.
• 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?

### Naive Multiplication

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

### Naive Exponentiation

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

#### A “Small” Change

• 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?