1. Limited time only! Sign up for a free 30min personal 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!

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




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