Imprint | Privacy Policy

Complexity Example

(Usage hints for this presentation)

October 2019
Dr. Jens Lechtenbörger (License Information)

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

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

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

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.