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 :)

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