Consider f(n) = lg(n). What is the largest size n of the problem that can be solved in 1 second, assuming that the time required to solve the problem takes f(n) microseconds? How to start?

- anonymous

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- anonymous

So you want the value that will make lg(n) = 1 second or 1000000 microsecond

- anonymous

I am still not sure how to proceed..

- ganeshie8

say n = 10^(10^6) then u wil get f(10^(10^6)) = log(10^(10^6)) us = 10^6 us = 1s

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- ganeshie8

so the largest size of problem that can be solved in 1s is \(10^{1000000}\)

- anonymous

10^6 us?? And why did you pick n = 10^(10^6)?

- ganeshie8

i just guessed, u can setup an equation aswell

- ganeshie8

we're given :- time required to solve the problem takes f(n) microseconds

- ganeshie8

so, if the problem size is n, then it takes f(n) microseconds

- ganeshie8

you need to solve the value of n, that makes f(n) = 1s

- ganeshie8

below eq'n :- 10^6 us = log(n)

- ganeshie8

remember that 10^6us = 1s

- ganeshie8

us = micro second

- anonymous

Ah! So, if it is one minute instead of one second, then it will be 60 x 10^6 us = lg(n) ?

- ganeshie8

thats it, all bigOh problems are just primitive accounting problems lol

- anonymous

Accounting is way easier than this. I just can't comprehend the problem. :(

- ganeshie8

did u get the phrase 'size of problem' ?

- anonymous

No, not at all.

- ganeshie8

okay, suppose i give u \(10\) different numbers and ask you to sort them

- ganeshie8

we say, the size of this problem is \(10\)

- ganeshie8

and lets say, u take 1 minute to solve them.

- ganeshie8

next, suppose i give u 1000000 numbers and ask u to sort them this time u wil take more time, but how much time u wil take depends on wat algorithm u use to sovle them.

- ganeshie8

here problem size is 1000000

- ganeshie8

'problem size' and 'data size' both refer to same thing.

- ganeshie8

see if that seems plausible

- anonymous

Ugh! Why is it not this: \[\frac{\lg n}{1}=\frac{1}{\lg n \times 10^{-6}}\]

- ganeshie8

dint get u ?

- anonymous

Ah! Not that one.. No./Size of problem Time Given 1 lg(n) x 10^(-6) Find n 1 So, we get \[\frac{1}{n} = \frac{\lg n\times 10^{-6}}{1}\]

- ganeshie8

n = 1 is undefined i guess, cuz it wud make the time 0

- ganeshie8

consider the cases n > 1, and use bit common sense

- ganeshie8

if a thing is done in 1us, and we're given the relation that f(n) = log(n) give time for doing n things, finding how many things we can do in 1s should be a high-school grade problem. i dont see any point in you pondering over it :|

- anonymous

" required to solve the problem takes f(n) microseconds" Isn't it lg(n) us instead of 1 us?

- ganeshie8

yes ur right

- anonymous

Also, if 1 thing is done in lg(n) us, and n things done in 1s, then we can set the equation \[\frac{1}{\lg (n) \times 10^{-6}}=\frac{n}{1}\]Right? Wrong?

- ganeshie8

oops sorry, looks i was sounding bit offensive earlier

- anonymous

It's ok...

- ganeshie8

10^6 us = log(n) whats the problem wid this equation ?

- anonymous

I don't understand how you get this equation, and I don't understand why mine is not correct.

- ganeshie8

same is the case wid me, gimme a sec to digest ur equation

- ganeshie8

wid ur equaiton, wats the largest size you're getting ?

- ganeshie8

we may plug that number in reverse and see if it works or not

- anonymous

Getting something weird with my equation. \[\frac{1}{\lg (n) \times 10^{-6}}=\frac{n}{1}\]\[n\lg (n) \times 10^{-6}=1\]\[\lg (n^n) =10^6\]\[n^n=10^{10^6}\] Don't know how to solve this thing..

- ganeshie8

humm ok, ima have dinner... wil get back and have a look at this again :)

- ganeshie8

read it like below :- Also, if \(\color{red}{n}\) things are done in lg(n) us, then find how many things can be done in 1s

- anonymous

\[\frac{n}{\lg n \times 10^{-6}} = \frac{N}{1}\] N = Number of things done in one second.

- ganeshie8

still stuck on this ha ?

- anonymous

Yes...

- ganeshie8

okay, i tried but im not getting ur equation, wat u trying to do wid that equation can u explain ?

- ganeshie8

we're given n things take log(n) micro seconds, and asked to find out how many things we can do in in 1 second so we simply sovle the equation log(n) = 10^6us

- ganeshie8

that gives the 'n' value corresponding to 10^6 us

- anonymous

It's like, you need 4 dollars to buy a bar of chocolate, how many bars of chocolate you can buy when you have 120 dollars? We can have \[\frac{1}{4}=\frac{n}{120}\]

- ganeshie8

thats right, wat if it takes log(n) dollars to buy n chocolates ?

- ganeshie8

and you're asked to find how many u can buy wid a million dollars money ?

- ganeshie8

the price per chocolate is not fixed here, clearly it depends on how many u buy

- anonymous

\[\frac{n}{\log n}=\frac{N}{1,000,000}\]?

- ganeshie8

its not a linear scaling, i dont think you can do it that way

- ganeshie8

first tell me this, are u convinced 10^(10^6) is the largest problem size yet ?

- anonymous

How do you know if it is the largest?

- ganeshie8

plugin that number in the given function

- anonymous

It works, but that does not guarantee there is no other (larger) solution, does it?

- ganeshie8

add 1 to that that, and plugin, wat do u get ?

- ganeshie8

u will get 1s + for any value larger than 10^(10^6) cuz log(n) is a strictly increasing function

- ganeshie8

but u want to complete job within 1s, so..

- anonymous

Ah! Ok...

- ganeshie8

the question is begging us to solve f(n) = log(n) = 10^6 no more than that.

- ganeshie8

if it helps seeing this, let me plot the time Vs problem-size graph quick

- ganeshie8

|dw:1389594869323:dw|

- ganeshie8

|dw:1389594972424:dw|

- ganeshie8

time to complete the job, depends on teh size of job

- ganeshie8

so ive put time in y-axis and size in x-axis. see if that makes more/less sense

- anonymous

It makes more sense :) Let say, if f(n) = n, will the graph then be |dw:1389595232578:dw|

- ganeshie8

yup, if its linear then we can use ur proportion :)

- ganeshie8

however most algorithms we deal with are exponential/logarthmic/polynomial there will be very few that scale linearly

- anonymous

How... do... you... know.... it ... is related to algorithms?

- ganeshie8

here, f(n) = log(n) represents how time scales as size increases for doing a 'particular job' using a 'particular algorithm'

- anonymous

I should have re-worded the question in a better way :\ So, give a function f(n) and time t seconds, we have f(n) = t x 10^6 Can I generalize the solution to this problem in this way?

- ganeshie8

dint get u

- ganeshie8

given : t = log(n) the inverse wud be :n = 10^t

- anonymous

The question can be generalized in this way: Consider f(n). What is the largest size n of the problem that can be solved in t seconds, assuming that the time required to solve the problem takes f(n) microseconds? And is the general solution/equation f(n) = t x 10^6 ?

- ganeshie8

general solution is to take inverse of time function

- ganeshie8

for our original probel :- given : t = log(n) the general solution (inverse )wud be :n = 10^t units are in microseconds

- ganeshie8

*problem

- ganeshie8

this may enhance ur understanding on complexity analysis http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html

Looking for something else?

Not the answer you are looking for? Search for more explanations.