Ace school

with brainly

  • Get help from millions of students
  • Learn from experts with step-by-step explanations
  • Level-up by helping others

A community for students.

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
See more answers at brainly.com
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.

Join Brainly to access

this expert answer

SEE EXPERT ANSWER

To see the expert answer you'll need to create a free account at Brainly

So you want the value that will make lg(n) = 1 second or 1000000 microsecond
I am still not sure how to proceed..
say n = 10^(10^6) then u wil get f(10^(10^6)) = log(10^(10^6)) us = 10^6 us = 1s

Not the answer you are looking for?

Search for more explanations.

Ask your own question

Other answers:

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

Not the answer you are looking for?

Search for more explanations.

Ask your own question