Thread: Big O (I think) & Sorts

Hey guys,

Could you guys help me with this problem.

Let f ( n ) = b + a n , where a is not equal to 0 , then O ( f ( n ) ) is
(a) O ( 1 )
(b) O ( a )
(c) O ( b )
(d) O ( n )
(e) O ( n^2 )

-----------------

Please check my answer(Bold):

Which of the following is NOT a true statement?
(a) The merge sort and insertion sort both divide the list into two equal sized subsets.
(b) The bubble sort compares elements that are adjacent to each other.
(c) The merge sort is more efficient than the insertion sort.
(d) Both (a) and (c)

O(n) because so it is bounded by a. Anything that is is also

Big O notation - Wikipedia, the free encyclopedia

Only a) is not true. Merge sort is certainly more efficient than insertion sort if implemented properly as it is O(n*log(n)) like quicksort. I am a big fan of merge sort, because it has much better worst case performance than quick sort. I especially like "natural merge sort", because in practice data you need to sort actually will tend to have some element of order anyway. Natural merge sort will profit from this but quick sort will not.