Algorithm Analysis

Big-Oh Notation

f(n)≤cg(n),for  n≤n0f(n) \leq cg(n), \quad for \; n\leq n_0

It is called as "f(n) is big-Oh of g(n)".

For example

  • 8n+58n+5 is O(n)O(n)

  • 5n4+3n3+2n2+4n+15n^4+3n^3+2n^2+4n+1 is O(n4)O(n^4)

  • a0+a1n+⋯+adnda_0+a_1n+\cdots+a_dn^d is O(nd)O(n^d)

  • 2n+100logn2n+100logn is O(n)O(n)

def find_max(data):
    # Return the maximum element from a nonempty Python list
    biggest = data[0] # The initial value to beat
    for val in data: # For each value:
        if val > biggest: # if it is greater than the best so far,
            biggest = val # we have found a new best (so far)
    return biggest # When loop ends, biggest is the max
    
  • initialization: O(1)

  • loop: O(n)

  • return: O(1)

To sum up, this algorithm has O(n) time complexity.

def prefix_average1(S):
    # Return list such tath, for all j, A[j] equals average of S[0], ..., S[j]
    n = len(S)
    A = [0]*n     # Create new list of n zeros
    for j in range(n):
        total = 0    # begin computing S[0]+...+S[j]
        for i in range(j+1):
            total += S[i]
        A[j] = total / (j+1)    # record the average
    return A

The running time of prefix_average1 is O(n2)O(n^2)

def prefix_average2(S):
    n = len(S)
    A = [0]*n
    for j in range(n):
        A[j] = sum(S[0:j])/(j+1)
    return A

This big-Oh notation is used widely to characterize running times and space bounds in terms of some parameter n. (prefix_average2 is also O(n2)O(n^2))

def prefix_average3(S):
    n = len(S)
    A = [0] * n
    total = 0
    for j in range(n):
        total += S[j]
        A[j] = total / (j+1)
    return A

The above expression only has O(n)O(n)time complexity.

Time complexity in Python

  • len(data): O(1)

  • data[j]: O(1)

Python's lists are implemented as array-based sequences.

Last updated

Was this helpful?