Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

F(n) = log n t = 1 seconds

  1. Feb 3, 2012 #1
    Hi,

    I'm doing this algorithm questions and i need to find the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.

    For example:

    f(n) = log n
    t = 1 seconds

    how do i get the largest size of n in t time??

    what i did is assume log is base 10, then:

    lg x = y
    x= 10^y
    since:
    f(n) = 1,000,000 microseconds
    n = 10^1,000,000

    am i right??

    you can refer to the Q here: http://problems.datastructures.net/database/problems/compare-running-times/compare-running-times.pdf
     
  2. jcsd
  3. Feb 3, 2012 #2

    Char. Limit

    User Avatar
    Gold Member

    Re: Logarithmn

    Well, first things first, you need to read the question a bit more carefully. The opening states clearly:

    Other than that, you should be on the right track.
     
  4. Feb 3, 2012 #3
    Re: Logarithmn

    oh my.. tks

    if it's base 2, then:

    lg2 x = y
    x= 2^y
    since:
    f(n) = 1,000,000 microseconds
    n = 2^1,000,000

    but why is the ans 10^3000000??
     
  5. Feb 4, 2012 #4

    Mentallic

    User Avatar
    Homework Helper

    Re: Logarithmn

    Do you mean 10300,000 as opposed to 103,000,000? If

    [tex]2^{10^6}=10^x[/tex]

    find x.
     
  6. Feb 4, 2012 #5
    Re: Logarithmn

    sorry i meant 300,000

    since:
    2^(10^6) = 10^x
    That means:
    since x = 10^6, therefore 10^x = 10^(10^6). but how do i get the value 10^300000??
     
    Last edited: Feb 4, 2012
  7. Feb 4, 2012 #6

    Char. Limit

    User Avatar
    Gold Member

    Re: Logarithmn

    Not... quite. You have to take the log base 10 to isolate x, and then you get 10^6 log_10(2), or about 1000000 * log_10(2). That's the x you're looking for, and it's easy to prove that it's about 300000. Then you get that 2^(10^6) is about equal to 10^(300000).
     
  8. Feb 4, 2012 #7
    Re: Logarithmn

    hi char.limit, may i know which log rule define this??
     
  9. Feb 4, 2012 #8

    Mentallic

    User Avatar
    Homework Helper

    Re: Logarithmn

    If

    [tex]a^b=c[/tex]

    then

    [tex]b=\log_ac[/tex]

    So can you apply this to your example?
     
  10. Feb 4, 2012 #9
    Re: Logarithmn

    sorry but im actually still confuse.. i dont really understand when char.limit said i can isolate x by taking log_10 of x and i get 106 . log_10 (2).

    i change x->y to avoid confusion. since the rule says:
    y = log_10 x, then x=10y

    if we continue from
    2106 =10y
    then
    y = log_10(2(106)) ????
    but how did char.limit get log_10(2).106??
     
    Last edited: Feb 4, 2012
  11. Feb 4, 2012 #10
    Re: Logarithmn

    Hi,

    i finally understood. the rule that i was looking for is
    loga(Xy) = y.loga(X)

    therefore,
    2106 =10y
    y = 106 . log10(2)

    However, i got another Q. if the Q was asked to use log2, must we give the final ans in log10??
     
  12. Feb 4, 2012 #11

    Mentallic

    User Avatar
    Homework Helper

    Re: Logarithmn

    Yes, that's right :smile:

    No, it's not necessary. I'd usually leave the answer as it is unless I was specifically asked to convert it into that form.
     
  13. Feb 4, 2012 #12
    Re: Logarithmn

    hmm okay tks alot peeps
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: F(n) = log n t = 1 seconds
Loading...