Register to reply

F(n) = log n t = 1 seconds

by nuttynibbles
Tags: logarithm
Share this thread:
nuttynibbles
#1
Feb3-12, 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...ning-times.pdf
Phys.Org News Partner Mathematics news on Phys.org
Math journal puts Rauzy fractcal image on the cover
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Char. Limit
#2
Feb3-12, 11:32 PM
PF Gold
Char. Limit's Avatar
P: 1,956
Quote Quote by nuttynibbles View Post
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...ning-times.pdf
Well, first things first, you need to read the question a bit more carefully. The opening states clearly:

Note that log n means the logarithm in base 2 of n.
Other than that, you should be on the right track.
nuttynibbles
#3
Feb3-12, 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??

Mentallic
#4
Feb4-12, 12:01 AM
HW Helper
P: 3,562
F(n) = log n t = 1 seconds

Quote Quote by nuttynibbles View Post
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??
Do you mean 10300,000 as opposed to 103,000,000? If

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

find x.
nuttynibbles
#5
Feb4-12, 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??
Char. Limit
#6
Feb4-12, 12:09 AM
PF Gold
Char. Limit's Avatar
P: 1,956
Quote Quote by nuttynibbles View Post
sorry i meant 300,000

since:
2^(10^6) = 10^x
That means:
10^(2^(10^6)) correct. but how do i calculate the value 10^300000?? i'll get error on my calculator
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).
nuttynibbles
#7
Feb4-12, 12:16 AM
P: 7
hi char.limit, may i know which log rule define this??
Mentallic
#8
Feb4-12, 03:06 AM
HW Helper
P: 3,562
Quote Quote by nuttynibbles View Post
hi char.limit, may i know which log rule define this??
If

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

then

[tex]b=\log_ac[/tex]

So can you apply this to your example?
nuttynibbles
#9
Feb4-12, 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 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??
nuttynibbles
#10
Feb4-12, 09:50 AM
P: 7
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??
Mentallic
#11
Feb4-12, 12:50 PM
HW Helper
P: 3,562
Quote Quote by nuttynibbles View Post
Hi,

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

therefore,
2106 =10y
y = 106 . log10(2)
Yes, that's right

Quote Quote by nuttynibbles View Post
However, i got another Q. if the Q was asked to use log2, must we give the final ans in log10??
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.
nuttynibbles
#12
Feb4-12, 09:21 PM
P: 7
hmm okay tks alot peeps


Register to reply