Question

lecture8(memory and search methods):
how is the number of times merge is called equal to log(len(list)) ??

Answer 1

Without going into the specifics of the memory and search methods (please post the MIT module you are referring to -- there are now two MIT 6.00 classes as well as your code) a function would have a logarithmic order if each time through the loop you divide by a factor.

For example if each time you are halving the loop that would be a logarithmic function.

Hope this helps.

Answer 2

This is because you divide the list into two each time you call merge sort. The number of calls is about log(len(list)), base 2 because of this division.

Answer 3

@kcpaas is correct. If you're not getting this, manually write out a list of 8 or 16 elements. Hand-simulate the algorithm, and see how many times you divide the list in two (refer back ot the lecture, or to http://en.wikipedia.org/wiki/Merge_sort , to see how the algorithm works). You'll notice the number of times you divide the list in two is equal also to the number of times you'll need to merge the list back together.

In fact what it turns out is you'll always be dividing the list in two until you get down to one or two elements to sort, and this works out to be \[\log_2 (num\; elements\; in\; list) \]

You'll also have to merge the same number of times, so this ends up being 2*log_2, but remember in big O notation we drop the cofactors. I gave a recitation on this you can see in the optional recitation video here: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-2/lecture-12-introduction-to-simulation-and-random-walks/#?w=535 I've attached to this post the handout from that recitation as I don't believe it was posted to OCW (working on this!)