# Thread: Big O (I think) & Sorts

1. ## 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 )

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

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)

2. O(n) because $lim_{n\rightarrow \infty}|\frac{f(n)}{n}|=lim_{n\rightarrow \infty}|\frac{b+an}{n}|=|a|$ so it is bounded by a. Anything that is $O(n)$ is also $O(n^2)$

Big O notation - Wikipedia, the free encyclopedia

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