Anaylyzing Algorithms Using The "Big-Oh" Notation (Data Structure and Algorithms in Python #1003)

Anaylyzing Algorithms Using The "Big-Oh" Notation


Let us design a python program find_max(s) which takes a sequence of numbers as the parameter and computes the maximum element.


def find_max(s):
    largest = s[0] # assume the first element be the largest
    for e in s: # iterate through the sequence
        if e > largest:
            largest = e
 return largest


Analysis: when find_max is invoked, the initialization before the for loop requires only a constant number of primitive operations, we denote this constant number c'. For each iteration of the loop, it also requires a constant number of primitive operations, and we denote this number c''. For the loop executes n times, so we can say the total number of primitive operations can be written as: c' + c''·n. So by the definition of “Big-Oh” notation, we could say this find_max() algorithm runs in O(n) time.


Comments

Popular posts from this blog

How to create a memory puzzle game with Python and Pygame (#005)

How to write a slide puzzle game with Python and Pygame (2020 tutorial)

Introduction to multitasking with Python #003 gevent (2020 tutorial)