Register to reply 
F(n) = log n t = 1 secondsby nuttynibbles
Tags: logarithm 
Share this thread: 
#1
Feb312, 11:30 PM

P: 7

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/d...ningtimes.pdf 


#2
Feb312, 11:32 PM

PF Gold
P: 1,945




#3
Feb312, 11:38 PM

P: 7

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?? 


#4
Feb412, 12:01 AM

HW Helper
P: 3,515

F(n) = log n t = 1 seconds
[tex]2^{10^6}=10^x[/tex] find x. 


#5
Feb412, 12:07 AM

P: 7

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?? 


#6
Feb412, 12:09 AM

PF Gold
P: 1,945




#7
Feb412, 12:16 AM

P: 7

hi char.limit, may i know which log rule define this??



#8
Feb412, 03:06 AM

HW Helper
P: 3,515

[tex]a^b=c[/tex] then [tex]b=\log_ac[/tex] So can you apply this to your example? 


#9
Feb412, 09:26 AM

P: 7

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 10^{6} . log_10 (2).
i change x>y to avoid confusion. since the rule says: y = log_10 x, then x=10^{y} if we continue from 2^{106} =10^{y} then y = log_10(2^{(106)}) ???? but how did char.limit get log_10(2).10^{6}?? 


#10
Feb412, 09:50 AM

P: 7

Hi,
i finally understood. the rule that i was looking for is log_{a}(X^{y}) = y.log_{a}(X) therefore, 2^{106} =10^{y} y = 10^{6} . log_{10}(2) However, i got another Q. if the Q was asked to use log_{2}, must we give the final ans in log_{10}?? 


#11
Feb412, 12:50 PM

HW Helper
P: 3,515




#12
Feb412, 09:21 PM

P: 7

hmm okay tks alot peeps



Register to reply 