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