What are the Big-Oh complexities of these tasks?

Question

I have the following question as part of my revision for a final exam:

For each of the following problems give the worst-case running time in
Big-O notation.

(i) Adding n numbers
(ii) Finding the minimum of n numbers in an unordered array 
(iii) Finding an item in a binary heap 
(iv) Sorting an unordered list of items using merge sort
(v) Finding the median (The value of a numerical set that equally divides
the number of values that are larger and smaller) of an array of sorted
items 

Are my current ideas correct?

(i) This would be O(n) because you are adding n numbers.
(ii) This again would be O(n). You have to check every element in this list.
(iii) Not 100% sure here, but i assume it would be worst case O(n log n) as most things are with binary heaps.
(iv) This would be O(n log n)
(v) Again i am not sure on this, maybe O(log n) since the array is sorted so you only need to search half the values, essentially a binary chop.

Could anybody point me in the right direction if any of my answers are incorrect.

Thanks, Chris.

Answer 1

(v) Finding the median (The value of a numerical set that equally divides the number of values that are larger and smaller) of an array of sorted items

(v) Again i am not sure on this, maybe O(log n) since the array is sorted so you only need to search half the values, essentially a binary chop.

This one is O(1). You are interested in the item that is in the middle of the sorted array (for N odd), or the average of the two "closest" to the middle (for N even).

Since the data is ordered, you can simply examine the one or two elements needed for the result.

Answer 2

(iii) Finding an item in a binary heap

(iii) Not 100% sure here, but i assume it would be worst case O(n log n) as most things are with binary heaps.

This is actually O(N) as it can be solved by a traversal of the binary tree the heap is built on.