Learn AI With Me: Big-O notation

Big-O notation describe how quickly runtime grow relatively to the input as the input get arbitrarily large.

Now we want to develop a notation to objectively compare the efficiency of these two algorithms. A good place to start would be to compare the number of assignments each algorithm makes.

The original sum1 function will create an assignment n+1 times, we can see this from the range based function. This means it will assign the final_sum variable n+1 times. We can then say that for a problem of n size (in this case just a number n) this function will take 1+n steps.

This n notation allows us to compare solutions and algorithms relative to the size of the problem, since sum1(10) and sum1(100000) would take very different times to run but be using the same algorithm. We can also note that as n grows very large, the +1 won't have much effect. So let's begin discussing how to build a syntax for this notation.

Now we will discuss how we can formalize this notation and idea.

Big-O notation describes how quickly runtime will grow relative to the input as the input get arbitrarily large.

Let's examine some of these points more closely:

Remember, we want to compare how quickly runtime will grows, not compare

Remember, we want to compare how quickly runtime will grows, not compare exact runtimes, since those can vary depending on hardware.
Since we want to compare for a variety of input sizes, we are only concerned with runtime grow relative to the input. This is why we use n for notation.
As n gets arbitrarily large we only worry about terms that will grow the fastest as n gets large, to this point, Big-O analysis is also known as asymptotic analysis

As for syntax sum1() can be said to be O(n) since its runtime grows linearly with the input size. In the next lecture we will go over more specific examples of various O() types and examples. To conclude this lecture we will show the potential for vast difference in runtimes of Big-O functions.

Runtimes of Common Big-O Functions

Here is a table of common Big-O functions:

Now let's plot the runtime versus the Big-O to compare the runtimes. We'll use a simple matplotlib for the plot below.

from math import log

import numpy as np

import matplotlib.pyplot as plt

%matplotlib inline

plt.style.use('bmh')

# Set up runtime comparisons

n = np.linspace(1,10,1000)

labels = ['Constant','Logarithmic','Linear','Log Linear','Quadratic','Cubic','Exponential']

big_o = [np.ones(n.shape),np.log(n),n,n*np.log(n),n**2,n**3,2**n]

# Plot setup

plt.figure(figsize=(12,10))

plt.ylim(0,50)

for i in range(len(big_o)):

plt.plot(n,big_o[i],label = labels[i])

plt.legend(loc=0)

plt.ylabel('Relative Runtime')

plt.xlabel('n')

Note how much of a difference a Big-O efficiency can make for the same n value against the projected runtime! Clearly we want to choose algorithms that stay away from any exponential, quadratic, or cubic behavior!

Big-O Example

O(1) Constant:

def fun_constant(values):

'''

Print the first item in a list of values.

'''

print(values[0])

> fun_constant([1,2,3,4])

This funstion is constant regardless of the list size. The function will only take a constant step size in this case 1, printing the first value from the list. So we can see here that an list of 100 values will print 1, list 10,000 values will print 1 and a list of n value will also print 1 item!

O(n) Linear:

def fun_linear(values):

'''

Print all the values in the list

'''

for x in values:

print(x)

> fun_linear([1,2,3,4,5])

This function runs O(n) linear time. This means that the number of operation taking place scales linearly with n, So we can see here that an input list of 100 values will print 100 times, 10,000 list of values will print 10,000 times and n number of values will print n times.

O(n^2) Quadratic:

def fun_Quadratic(values):

'''

This will print pairs of every items in the list

'''

for x in values:

for y in values:

print(x, y)

> fun_Quadratic([1,2,3,4,5])

1 1

1 2

1 3

1 4

1 5

2 1

2 2

2 3

2 4

2 5

3 1

3 2

3 3

3 4

3 5

4 1

4 2

4 3

4 4

4 5

5 1

5 2

5 3

5 4

5 5

Note how we now have two loops, one nested inside another. This means that for a list of n items, we will have to perform n operations for every item in the list! This means in total, we will perform n times n assignments, or n^2. So a list of 10 items will have 10^2, or 100 operations. You can see how dangerous this can get for very large inputs! This is why Big-O is so important to be aware of!

O(n^3) Cubical:

def fun_cubical(values):

'''

This will print the value 3 times

'''

for x in values:

for y in values:

for z in values:

print(x,y,z)

> fun_cubical([1,2,3,4,5])

1 1 1

1 1 2

1 1 3

1 1 4

1 1 5

1 2 1

1 2 2

1 2 3

1 2 4

1 2 5

1 3 1

1 3 2

1 3 3

1 3 4

1 3 5

1 4 1

1 4 2

1 4 3

1 4 4

1 4 5

1 5 1

1 5 2

1 5 3

1 5 4

1 5 5

2 1 1

2 1 2

2 1 3

2 1 4

2 1 5

2 2 1

2 2 2

2 2 3

2 2 4

2 2 5

2 3 1

2 3 2

2 3 3

2 3 4

2 3 5

2 4 1

2 4 2

2 4 3

2 4 4

2 4 5

2 5 1

2 5 2

2 5 3

2 5 4

2 5 5

3 1 1

3 1 2

3 1 3

3 1 4

3 1 5

3 2 1

3 2 2

3 2 3

3 2 4

3 2 5

3 3 1

3 3 2

3 3 3

3 3 4

3 3 5

3 4 1

3 4 2

3 4 3

3 4 4

3 4 5

3 5 1

3 5 2

3 5 3

3 5 4

3 5 5

4 1 1

4 1 2

4 1 3

4 1 4

4 1 5

4 2 1

4 2 2

4 2 3

4 2 4

4 2 5

4 3 1

4 3 2

4 3 3

4 3 4

4 3 5

4 4 1

4 4 2

4 4 3

4 4 4

4 4 5

4 5 1

4 5 2

4 5 3

4 5 4

4 5 5

5 1 1

5 1 2

5 1 3

5 1 4

5 1 5

5 2 1

5 2 2

5 2 3

5 2 4

5 2 5

5 3 1

5 3 2

5 3 3

5 3 4

5 3 5

5 4 1

5 4 2

5 4 3

5 4 4

5 4 5

5 5 1

5 5 2

5 5 3

5 5 4

5 5 5

Note now we have 3 loops nested inside one another.so, a list of 10 values will have 10^3 which is 1000 operation!

log(n) Logarithmic:

def fun_logarithmic(values):

'''

range(start, stop, step)

start Optional. An integer number specifying at which position to start. Default is 0

stop Required. An integer number specifying at which position to stop (not included).

step Optional. An integer number specifying the incrementation. Default is 1

'''

for x in range(0,len(values),4):

print(x)

>fun_logarithmic([1,2,3,4,5])

Here based on the inputes number of operations decrease. Algorithmic operations are commonly found in binary trees or when using binary search.

nlog(n) Log linear:

def fun_logLinear(values):

for x in values: # performs O(n) operations!

for y in range(x,len(values),4): # perform O(log(n)) operations!

print(x,y)

> fun_logLinear([1,2,3,4,5,6])

1 1

1 5

2 2

3 3

4 4

5 5

O(2^n) exponential:

def fun_exponential(value):

if value <=1:

return 1

else:

return fun_exponential(value -2) + fun_exponential(value -1)

> fun_exponential(6)

Calculating Scale of Big-O:

When it comes to Big O notation we only care about the most significant terms, remember as the input grows larger only the fastest growing terms will matter. If you've taken a calculus class before, this will reminf you of taking limits towards infinity. Let's see an example of how to drop constants:

def print_once(lst):

'''

Prints all items once

'''

for val in lst:

print(val)

> print_once([1,2,3,4,5,6])

The print_once() function is O(n) since it will scale linearly with the input. What about the next example?

def print_3(lst):

'''

Prints all items three times

'''

for val in lst:

print(val)

for val in lst:

print(val)

for val in lst:

print(val)

> print_3([1,2,3,4])

We can see that the first function will print O(n) items and the second will print O(3n) items. However for n going to inifinity the constant can be dropped, since it will not have a large effect, so both functions are O(n).

Let's see a more complex example of this:

def comp(lst):

'''

This function prints the first item O(1)

Then is prints the first 1/2 of the list O(n/2)

Then prints a string 10 times O(10)

'''

print(lst[0])

midpoint = len(lst)/2

for val in range(lst[int(midpoint)]):

print(val)

for x in range(10):

print('number')

> comp([1,2,3])

number

[ ]

Introduction to Algorithm analysis and Big "O"

Why Algorithm Analysis

Before we begin, let's clarify what an algorthim 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 procdures 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 seperate functions:

[ ]

12345678910

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)

[ ]

12345

def sum2(n):

'''

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

'''

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

[ ]

sum2(10)

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)

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 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!

Big-O notation

Big-O notation describe how quickly runtime grow relatively to the input as the input get arbitrarily large.

Now we want to develop a notation to objectively compare the efficiency of these two algorithms. A good place to start would be to compare the number of assignments each algorithm makes.

Now we will discuss how we can formalize this notation and idea.

Big-O notation describes how quickly runtime will grow relative to the input as the input get arbitrarily large.

Let's examine some of these points more closely:

Remember, we want to compare how quickly runtime will grows, not compare

Remember, we want to compare how quickly runtime will grows, not compare exact runtimes, since those can vary depending on hardware.

Since we want to compare for a variety of input sizes, we are only concerned with runtime grow relative to the input. This is why we use n for notation.

As n gets arbitrarily large we only worry about terms that will grow the fastest as n gets large, to this point, Big-O analysis is also known as asymptotic analysis

As for syntax sum1() can be said to be O(n) since its runtime grows linearly with the input size. In the next lecture we will go over more specific examples of various O() types and examples. To conclude this lecture we will show the potential for vast difference in runtimes of Big-O functions.

Runtimes of Common Big-O Functions

Here is a table of common Big-O functions:

image.png

Now let's plot the runtime versus the Big-O to compare the runtimes. We'll use a simple matplotlib for the plot below.

[ ]

12345678910111213141516171819202122

from math import log

import numpy as np

import matplotlib.pyplot as plt

%matplotlib inline

plt.style.use('bmh')

# Set up runtime comparisons

n = np.linspace(1,10,1000)

labels = ['Constant','Logarithmic','Linear','Log Linear','Quadratic','Cubic','Exponential']

big_o = [np.ones(n.shape),np.log(n),n,n*np.log(n),n**2,n**3,2**n]

…plt.ylabel('Relative Runtime')

plt.xlabel('n')

Big-O Example

↳ 28 cells hidden

Calculating Scale of Big-O

[ ]

123456

def print_once(lst):

'''

Prints all items once

'''

for val in lst:

print(val)

[ ]

print_once([1,2,3,4,5,6])

The print_once() function is O(n) since it will scale linearly with the input. What about the next example?

[ ]

123456789101112

def print_3(lst):

'''

Prints all items three times

'''

for val in lst:

print(val)

for val in lst:

print(val)

for val in lst:

print(val)

[ ]

print_3([1,2,3,4])

Let's see a more complex example of this:

[ ]

1234567891011121314

def comp(lst):

'''

This function prints the first item O(1)

Then is prints the first 1/2 of the list O(n/2)

Then prints a string 10 times O(10)

'''

print(lst[0])

midpoint = len(lst)/2

for val in range(lst[int(midpoint)]):

print(val)

for x in range(10):

print('number')

[ ]

comp([1,2,3])

So let's break down the operations here. We can combine each operation to get the total Big-O of the function:

O(1+n/2+10)

We can see that as n grows larger the 1 and 10 terms become insignificant and the 1/2 term multiplied against n will also not have much of an effect as n goes towards infinity. This means the function is simply O(n)!

Learn AI With Me

Search

Big-O notation

Runtimes of Common Big-O Functions

Big-O Example

O(1) Constant:

O(n) Linear:

O(n^2) Quadratic:

O(n^3) Cubical:

log(n) Logarithmic:

nlog(n) Log linear:

O(2^n) exponential:

Calculating Scale of Big-O:

No comments:

Post a Comment

Contact Form

Wikipedia

Total Pageviews

Translate

Followers