hw assignment help on selection & merge sort

[jack223]

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

[Narue]

>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.

[Rashakil Fol]

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.

[Rashakil Fol]

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.

[jack223]

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....

[Rashakil Fol]

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

[poojabi]

@rashakil fol
how to to count the number of comparison in merge sort.even i am confused with this comparison thing.can u tell me how to count comparison of binary insertion sort.

[Adak]

You've replied to a thread that is 4 years old. I doubt the OP is still expecting an answer and will read your post.

Start a new thread for your top, so it will get noticed, and get some answers. A comparison is made whenever you compare the value of one number in the array, with the value of another number in the array.

Can't really say it any clearer than that. ;)