Complexity Example

Sample Algorithms

• 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.
  • 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:
        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))

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

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?

License Information

No warranties are given. The license may not give you all of the permissions necessary for your intended use.

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.