1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Asymptotic time complexity

  1. Aug 8, 2014 #1

    Maylis

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    In this question you will determine the asymptotic time complexity of an algorithm for which the complexity is ##T(n)=n^{2}+3##.

    Find a positive real c and a positive integer ##k##, such that

    ##T(n) \le cf(n)##

    holds for all ## n>k ## if ##f(n) ## is the asymptotic time complexity.

    What is the best choice for ##f(n)##?

    [ans]

    What is a good choice for ##c## such that ##k## is small (i.e. less than 10)?


    What is ##k##?


    2. Relevant equations



    3. The attempt at a solution
    I am confused how to approach these problems. Unfortunately the choices for ##f(n)## are not visible, there is a bug in the problem. But I was wondering what I should do in order to do these problems. The notes are not adequate (or available to look at, since that is bugged as well).
     
  2. jcsd
  3. Aug 8, 2014 #2
    If there was a specific list of ##f(n)##'s that you don't have, then you're left guessing.
    Commonly, the ##f(n)## is pretty simple, such as ##f(n) = e^n##, ##n^3##, or ##n^2##.

    Among those choices, ##f(n) = n^2## would be best. Then use a c of 1.5 and a k of 3.
     
  4. Aug 8, 2014 #3

    Maylis

    User Avatar
    Gold Member

    You mean there is no way to analytically choose it?

    The bug has been fixed, so the choices are
    ##n^2##, ##n##, ##nlog(n)##, and ##n^3##, so I pick ##n^2## since that is the closest to ##n^2 + 3##. Next, for ##k## being small (less than 10), I just do ## k = 9## and all ##n \gt 9##.

    The choices for ##c## are 5, 0.5, 2, and 1, so I pick 2 since the inequality ##n^2 + 3 \le 2n^2## will be true for all ##n > 9##.

    Next they ask what ##k## is, and the choices are 1, 10, 2, and 5. Well, what the heck do I do for that??
     
    Last edited: Aug 8, 2014
  5. Aug 9, 2014 #4
    Hey, I didn't do too bad at picking an ##f(n)## and ##c## without knowing the choices! Did I?

    They want ##T(n)≤cf(n)## for all ##n>k##.
    with ##T(n)=n^2+3## and ##cf(n)=2(n^2)##.
    So, we have ##n^2+3 <= 2n^2## for all ##n>k##.

    Clearly, if ##n=0##, then ##0^2+3 <= 2(0^2)##, so ##3<=0##, which is false. So ##n=0## doesn't work.

    Let me know if you can't take it from there - I'll walk you through the rest.
     
  6. Aug 9, 2014 #5

    Maylis

    User Avatar
    Gold Member

    The problem I have with this is that when you pick ##c##, it's almost as if you are simultaneously supposing a ##k##. Are you supposed to pick the ##c## without regards to a possible ##k##?
     
  7. Aug 9, 2014 #6
    What you should notice is that as long as ##c## is greater than 1, there will be a ##k##. If ##c## is one or less, then ##T(N)## will always be greater than ##cf(n)##. So, without a list to choose from, I picked ##c=1.5## which would have required ##n>2 (k=2)##. Notice that in this case, even a ##c## that is slightly above 1, allows k to be fairly small.
    This is pretty much just an academic exercise. For most real applications, it would be good enough to say that it was approximates ##cn^2## without worrying about the exact value of ##c##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Asymptotic time complexity
Loading...