[Tutor] the big o

[Alan Gauld]

On 28/07/15 02:30, Quiles, Stephanie wrote:
> question asks give the big-o performance of the following code fragment:
>
> for i in range(n):
> 	for j in range(n):
> 		k = 2 + 2
>
> > ...i still cannot grasp the big-o.


The big O is a way of describing the relative performance
of an algorithm. For example if you have a random list
of N values and want to find a particular one you need to
search the list looking at each item until you find the one
you want. That could mean doing anything from 1-N lookups.
But on average it would be N/2 (Do you understand how I
got that value?) So the big-O performance of our search
is O(N/2) The result will, on average take N/2 operations.

Now if the list were sorted into ascending order we can
speed that up significantly by using an algorithm called
a binary-chop. That means we start by looking at the middle
item and seeing if it is bigger or smaller than our search
item. If its smaller we can limit the search to the lower
half of the list. We now apply the binary chop again and
once more limit the list to half of the new list. Eventually
we get a list of one item which contains our item(assuming
it existed of course!) It turns out the number of chops we
need is log2(N) (ie for 16 items we need at most 4 chops
to find the item) So the algorithm is O(log2(N)) which is
faster than O(N/2)

Does that make sense so far?

Looking at your example you have a variable 'n' that controls
how many operations you will perform. Can you see how many
times the addition (k = 2+2) will be performed?
is it n?
is it 2*n
is it n*n?
something else?

The answer is your big-O value.

HTH
-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos