Results 1 to 3 of 3

Thread: Big O (I think) & Sorts

  1. #1
    Junior Member
    Sep 2008

    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)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Gamma's Avatar
    Dec 2008
    Iowa City, IA
    O(n) because $\displaystyle 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 $\displaystyle O(n)$ is also $\displaystyle O(n^2)$

    Big O notation - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member alunw's Avatar
    May 2009
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. An integration of sorts.
    Posted in the Calculus Forum
    Replies: 5
    Last Post: Sep 10th 2008, 02:52 AM
  2. all sorts of algebra questions
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Jul 16th 2007, 05:33 AM
  3. Different Sorts (Bubble, Insertion...)
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: Oct 21st 2006, 11:55 PM

Search Tags

/mathhelpforum @mathhelpforum