Imprint | Privacy Policy

Complexity Example

(Usage hints for this presentation)

Winter Term 2020/2021
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 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.
        • If code does not execute, maybe reload without cache (Ctrl+F5 in Firefox)
        • 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?

License Information

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