Introduction to Algorithm analysis and Big "O"

    Why Algorithm Analysis:

Before we begin, let's clarify what an algorithm is. In this course, an algorithm is simply a procedure or formula for solving a problem. Some problems are famous enough that the algorithms have names, as well as some procedures being common enough that the algorithm associated with it also has a name. So now we have a good question we need to answer:

How do analyze algorithms and how can we compare algorithms against each other?

Imagine if you and a friend both came up with functions to sum the numbers from 0 to N. How would you compare the functions and algorithms within the functions? Let's say you both cam up with these two separate functions:

def sum1(n):

  '''

  Take the input n and the return the sum of numbers from 0 to n

  '''

  final_sum = 0

  for x in range(n+1):

    final_sum += x

  return final_sum

-> sum1(10)

55

def sum2(n):

  '''

  Take input n and return the sum of numbers from 0 to n

  '''

  return (n*(n+1)/2)

-> sum2(10)

55.0

You'll notice both functions have the same result, but completely different algorithms. You'll note that the first function iteratively adds the numbers, while the second function makes use of:

∑i=0ni=n(n+1)2

So how can we objectively compare the algorithms? We could compare the amount of space they take in memory or we could also compare how much time it takes each function to run.

Let's go ahead and compare the time it took to run the functions:

-> %timeit sum1(100)

100000 loops, best of 3: 4.03 µs per loop

The slowest run took 5.15 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 4.86 µs per loop

->%timeit sum2(100)

The slowest run took 17.41 times longer than the fastest. This could mean that an intermediate result is being cached.

10000000 loops, best of 3: 117 ns per loop

The slowest run took 16.54 times longer than the fastest. This could mean that an intermediate result is being cached 10000000 loops, best of 3: 173 ns per loop We can see that the second function is much more efficient! Running at a much faster rate than the first. However, we can not use "time to run" as an objective measurement, because that will depend on the speed of the computer itself and hardware capabilities. So we will need to use another method, Big-O!