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 _______________________________________________ Tutor maillist - [email protected] To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
