hw assignment help on selection & merge sort
 

It's from my homework assignment

Question 1)
Based on the O notation, approximately how many swaps and comparisons occur when Selection sort is called on a worst-case array of length 8?

a) 16
b) 64
c) 100
d) 800

Number of swaps = O(n) which is "8" and
Number of comparison = O(n^2) which is "64".

I'm little bit counfused of what the question is asking??? am I suppose to choose more than one answer??


Question 2)
Approximately how many swaps and comparisons occur when Merge Sort is called on a worst-case array of length 8?

a) 8
b) 16
c) 24
d) 64

Number of swaps = O(N log N) or Log2 N which is "3" i think
Number of comparison O(N log N)or Log2 N



Can anybody show me to how to find swaps and comparisons for selection sort & merge sort..please.

thanks

Re: hw assignment help on selection & merge sort
 

>Based on the O notation, approximately how many swaps and
>comparisons occur when Selection sort is called on a worst-case array of length 8?
That's very poorly worded. Also, there's no such thing as a worst case for selection sort. The best, average, and worst cases are all identical.

Re: hw assignment help on selection & merge sort
 

Run the algorithms out by hand in the worst case scenario (you have to figure this out), and while doing so, count the number of swaps and comparisons made. This will be your answer. Troublingly, merge sort would not be implemented with any swapping... and selection sort with 8 elements has a worst case of 28 comparisons, 28 swaps, assuming you move values over by swapping successive pairs of values. (But if moving values is implemented more efficiently, you'll have only 1 instance of what could be called a 'swap'.) Now, 28+1 is closer to the answer 16 than 64, but I'm sure whoever asked this question thinks that '64' is the correct answer.

In conclusion, whoever wrote these questions is nearly an absolute idiot. They want you to go from O(N log N) to 8*log8 = 24? That's lunacy, and that number has nothing to do with the actual number of swaps made. For example, the exact answer to your second problem is 17 comparisons. (Merge sort algorithms generally do not implement any swapping.) I don't blame you for being confused; the questions are written by somebody who does not understand big O notation.

Big O notation says that a value will be no more than a certain _multiple_ of some expression. That multiple could be any positive number imaginable, so big O notation can't be used to get approximations to actual, numerical answers.

Re: hw assignment help on selection & merge sort
 

Another way of putting it is that the symbol O(N log N) has exactly the same meaning as O(50N log N). So would the expected answer be 24, or would it be 1200? This is why coming up with any value by plugging numbers into O notation expressions is completely meaningless.

Re: hw assignment help on selection & merge sort
 

hmm...i'm still confused!!
so the answer for the first question is "64"??
and the answer for the 2nd question is "24" or "16"?
i hate taking on-line classes....

Re: hw assignment help on selection & merge sort
 

Why do you care about the answer? The questions themselves are wrong.