Results 1 to 3 of 3

Math Help - Big O (I think) & Sorts

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    61

    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
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member alunw's Avatar
    Joined
    May 2009
    Posts
    188
    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: September 10th 2008, 03:52 AM
  2. all sorts of algebra questions
    Posted in the Algebra Forum
    Replies: 4
    Last Post: July 16th 2007, 06:33 AM
  3. Different Sorts (Bubble, Insertion...)
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: October 22nd 2006, 12:55 AM

Search Tags


/mathhelpforum @mathhelpforum