reset password
Author Message
G190852562
Posts: 162
Posted 20:55 Dec 06, 2014 |

1. I need explanation as to why the answer is A * n^2 + B * n + C. My understanding is that the loops involved in the code (http://www.java2novice.com/java-sorting-algorithms/merge-sort/) give the dominant term of n^2. 

4. From what I understand, doMergeSort basically splits the array into two, sorts the first half then merges these two sorted arrays. Why is log n involved in the answer A * n * log n + C? Is it because of the splitting of the array on line 30?

5. I believe that I got this problem wrong because I selected "average case analysis." Were the answers: worst case analysis, don't pay much attention to constant factors, and focus on running time for large input size?

Last edited by G190852562 at 21:02 Dec 06, 2014.
G190852562
Posts: 162
Posted 21:25 Dec 06, 2014 |

If you could post the questions next to the answers, that would make it much easier to answer. Rather than go back and forth between your question and quiz questions.

rabbott
Posts: 1649
Posted 21:26 Dec 06, 2014 |

Question 1 asked about MergeParts, not about the entire algorithm. Merge scans two lists of length no more than N. It processes each element once.

rabbott
Posts: 1649
Posted 21:27 Dec 06, 2014 |

Question 4 asked why a log function is involved. Each level of recursion works on lists that are half as long as the previous. So it takes log n levels of recursion to reduce the length from n to 1.

G190852562
Posts: 162
Posted 21:28 Dec 06, 2014 |

It'll be easier if we had the answers, so that we know if we are doing the problems correctly.

rabbott
Posts: 1649
Posted 21:28 Dec 06, 2014 |

Question 5 asked about the primary focus of the Coursera videos. You're right, average case analysis isn't one of them.

rabbott
Posts: 1649
Posted 21:29 Dec 06, 2014 |

More generally, as I said earlier, if you want to discuss a question, please post your thinking about it. We can discuss it then. Simply posting the answers is not the point. 

G190852562
Posts: 162
Posted 21:44 Dec 06, 2014 |

I have issues understanding the Merge Sort code quickly. It takes a very long while and I have to trace it line by line. Is this normal? And is there any suggestion to reading them more efficiently?