anonymous
  • anonymous
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?
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
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
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
So you want the value that will make lg(n) = 1 second or 1000000 microsecond
anonymous
  • anonymous
I am still not sure how to proceed..
ganeshie8
  • 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
  • ganeshie8
so the largest size of problem that can be solved in 1s is \(10^{1000000}\)
anonymous
  • anonymous
10^6 us?? And why did you pick n = 10^(10^6)?
ganeshie8
  • ganeshie8
i just guessed, u can setup an equation aswell
ganeshie8
  • ganeshie8
we're given :- time required to solve the problem takes f(n) microseconds
ganeshie8
  • ganeshie8
so, if the problem size is n, then it takes f(n) microseconds
ganeshie8
  • ganeshie8
you need to solve the value of n, that makes f(n) = 1s
ganeshie8
  • ganeshie8
below eq'n :- 10^6 us = log(n)
ganeshie8
  • ganeshie8
remember that 10^6us = 1s
ganeshie8
  • ganeshie8
us = micro second
anonymous
  • anonymous
Ah! So, if it is one minute instead of one second, then it will be 60 x 10^6 us = lg(n) ?
ganeshie8
  • ganeshie8
thats it, all bigOh problems are just primitive accounting problems lol
anonymous
  • anonymous
Accounting is way easier than this. I just can't comprehend the problem. :(
ganeshie8
  • ganeshie8
did u get the phrase 'size of problem' ?
anonymous
  • anonymous
No, not at all.
ganeshie8
  • ganeshie8
okay, suppose i give u \(10\) different numbers and ask you to sort them
ganeshie8
  • ganeshie8
we say, the size of this problem is \(10\)
ganeshie8
  • ganeshie8
and lets say, u take 1 minute to solve them.
ganeshie8
  • 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
  • ganeshie8
here problem size is 1000000
ganeshie8
  • ganeshie8
'problem size' and 'data size' both refer to same thing.
ganeshie8
  • ganeshie8
see if that seems plausible
anonymous
  • anonymous
Ugh! Why is it not this: \[\frac{\lg n}{1}=\frac{1}{\lg n \times 10^{-6}}\]
ganeshie8
  • ganeshie8
dint get u ?
anonymous
  • 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
  • ganeshie8
n = 1 is undefined i guess, cuz it wud make the time 0
ganeshie8
  • ganeshie8
consider the cases n > 1, and use bit common sense
ganeshie8
  • 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
  • anonymous
" required to solve the problem takes f(n) microseconds" Isn't it lg(n) us instead of 1 us?
ganeshie8
  • ganeshie8
yes ur right
anonymous
  • 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
  • ganeshie8
oops sorry, looks i was sounding bit offensive earlier
anonymous
  • anonymous
It's ok...
ganeshie8
  • ganeshie8
10^6 us = log(n) whats the problem wid this equation ?
anonymous
  • anonymous
I don't understand how you get this equation, and I don't understand why mine is not correct.
ganeshie8
  • ganeshie8
same is the case wid me, gimme a sec to digest ur equation
ganeshie8
  • ganeshie8
wid ur equaiton, wats the largest size you're getting ?
ganeshie8
  • ganeshie8
we may plug that number in reverse and see if it works or not
anonymous
  • 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
  • ganeshie8
humm ok, ima have dinner... wil get back and have a look at this again :)
ganeshie8
  • 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
  • anonymous
\[\frac{n}{\lg n \times 10^{-6}} = \frac{N}{1}\] N = Number of things done in one second.
ganeshie8
  • ganeshie8
still stuck on this ha ?
anonymous
  • anonymous
Yes...
ganeshie8
  • ganeshie8
okay, i tried but im not getting ur equation, wat u trying to do wid that equation can u explain ?
ganeshie8
  • 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
  • ganeshie8
that gives the 'n' value corresponding to 10^6 us
anonymous
  • 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
  • ganeshie8
thats right, wat if it takes log(n) dollars to buy n chocolates ?
ganeshie8
  • ganeshie8
and you're asked to find how many u can buy wid a million dollars money ?
ganeshie8
  • ganeshie8
the price per chocolate is not fixed here, clearly it depends on how many u buy
anonymous
  • anonymous
\[\frac{n}{\log n}=\frac{N}{1,000,000}\]?
ganeshie8
  • ganeshie8
its not a linear scaling, i dont think you can do it that way
ganeshie8
  • ganeshie8
first tell me this, are u convinced 10^(10^6) is the largest problem size yet ?
anonymous
  • anonymous
How do you know if it is the largest?
ganeshie8
  • ganeshie8
plugin that number in the given function
anonymous
  • anonymous
It works, but that does not guarantee there is no other (larger) solution, does it?
ganeshie8
  • ganeshie8
add 1 to that that, and plugin, wat do u get ?
ganeshie8
  • ganeshie8
u will get 1s + for any value larger than 10^(10^6) cuz log(n) is a strictly increasing function
ganeshie8
  • ganeshie8
but u want to complete job within 1s, so..
anonymous
  • anonymous
Ah! Ok...
ganeshie8
  • ganeshie8
the question is begging us to solve f(n) = log(n) = 10^6 no more than that.
ganeshie8
  • ganeshie8
if it helps seeing this, let me plot the time Vs problem-size graph quick
ganeshie8
  • ganeshie8
|dw:1389594869323:dw|
ganeshie8
  • ganeshie8
|dw:1389594972424:dw|
ganeshie8
  • ganeshie8
time to complete the job, depends on teh size of job
ganeshie8
  • ganeshie8
so ive put time in y-axis and size in x-axis. see if that makes more/less sense
anonymous
  • anonymous
It makes more sense :) Let say, if f(n) = n, will the graph then be |dw:1389595232578:dw|
ganeshie8
  • ganeshie8
yup, if its linear then we can use ur proportion :)
ganeshie8
  • ganeshie8
however most algorithms we deal with are exponential/logarthmic/polynomial there will be very few that scale linearly
anonymous
  • anonymous
How... do... you... know.... it ... is related to algorithms?
ganeshie8
  • ganeshie8
here, f(n) = log(n) represents how time scales as size increases for doing a 'particular job' using a 'particular algorithm'
anonymous
  • 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
  • ganeshie8
dint get u
ganeshie8
  • ganeshie8
given : t = log(n) the inverse wud be :n = 10^t
anonymous
  • 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
  • ganeshie8
general solution is to take inverse of time function
ganeshie8
  • ganeshie8
for our original probel :- given : t = log(n) the general solution (inverse )wud be :n = 10^t units are in microseconds
ganeshie8
  • ganeshie8
*problem
ganeshie8
  • 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.