A community for students. Sign up today!
Here's the question you clicked on:
 0 viewing
 11 months ago
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?
 11 months ago
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?

This Question is Closed

whereismymind49
 11 months ago
Best ResponseYou've already chosen the best response.0So you want the value that will make lg(n) = 1 second or 1000000 microsecond

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0I am still not sure how to proceed..

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1say n = 10^(10^6) then u wil get f(10^(10^6)) = log(10^(10^6)) us = 10^6 us = 1s

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1so the largest size of problem that can be solved in 1s is \(10^{1000000}\)

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.010^6 us?? And why did you pick n = 10^(10^6)?

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1i just guessed, u can setup an equation aswell

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1we're given : time required to solve the problem takes f(n) microseconds

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1so, if the problem size is n, then it takes f(n) microseconds

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1you need to solve the value of n, that makes f(n) = 1s

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1below eq'n : 10^6 us = log(n)

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1remember that 10^6us = 1s

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0Ah! So, if it is one minute instead of one second, then it will be 60 x 10^6 us = lg(n) ?

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1thats it, all bigOh problems are just primitive accounting problems lol

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0Accounting is way easier than this. I just can't comprehend the problem. :(

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1did u get the phrase 'size of problem' ?

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1okay, suppose i give u \(10\) different numbers and ask you to sort them

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1we say, the size of this problem is \(10\)

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1and lets say, u take 1 minute to solve them.

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1next, 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
 11 months ago
Best ResponseYou've already chosen the best response.1here problem size is 1000000

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1'problem size' and 'data size' both refer to same thing.

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1see if that seems plausible

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0Ugh! Why is it not this: \[\frac{\lg n}{1}=\frac{1}{\lg n \times 10^{6}}\]

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0Ah! 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
 11 months ago
Best ResponseYou've already chosen the best response.1n = 1 is undefined i guess, cuz it wud make the time 0

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1consider the cases n > 1, and use bit common sense

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1if 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 highschool grade problem. i dont see any point in you pondering over it :

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0" required to solve the problem takes f(n) microseconds" Isn't it lg(n) us instead of 1 us?

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0Also, 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
 11 months ago
Best ResponseYou've already chosen the best response.1oops sorry, looks i was sounding bit offensive earlier

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.110^6 us = log(n) whats the problem wid this equation ?

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0I don't understand how you get this equation, and I don't understand why mine is not correct.

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1same is the case wid me, gimme a sec to digest ur equation

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1wid ur equaiton, wats the largest size you're getting ?

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1we may plug that number in reverse and see if it works or not

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0Getting 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
 11 months ago
Best ResponseYou've already chosen the best response.1humm ok, ima have dinner... wil get back and have a look at this again :)

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1read 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

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0\[\frac{n}{\lg n \times 10^{6}} = \frac{N}{1}\] N = Number of things done in one second.

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1still stuck on this ha ?

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1okay, i tried but im not getting ur equation, wat u trying to do wid that equation can u explain ?

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1we'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
 11 months ago
Best ResponseYou've already chosen the best response.1that gives the 'n' value corresponding to 10^6 us

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0It'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
 11 months ago
Best ResponseYou've already chosen the best response.1thats right, wat if it takes log(n) dollars to buy n chocolates ?

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1and you're asked to find how many u can buy wid a million dollars money ?

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1the price per chocolate is not fixed here, clearly it depends on how many u buy

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0\[\frac{n}{\log n}=\frac{N}{1,000,000}\]?

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1its not a linear scaling, i dont think you can do it that way

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1first tell me this, are u convinced 10^(10^6) is the largest problem size yet ?

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0How do you know if it is the largest?

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1plugin that number in the given function

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0It works, but that does not guarantee there is no other (larger) solution, does it?

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1add 1 to that that, and plugin, wat do u get ?

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1u will get 1s + for any value larger than 10^(10^6) cuz log(n) is a strictly increasing function

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1but u want to complete job within 1s, so..

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1the question is begging us to solve f(n) = log(n) = 10^6 no more than that.

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1if it helps seeing this, let me plot the time Vs problemsize graph quick

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1dw:1389594869323:dw

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1dw:1389594972424:dw

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1time to complete the job, depends on teh size of job

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1so ive put time in yaxis and size in xaxis. see if that makes more/less sense

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0It makes more sense :) Let say, if f(n) = n, will the graph then be dw:1389595232578:dw

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1yup, if its linear then we can use ur proportion :)

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1however most algorithms we deal with are exponential/logarthmic/polynomial there will be very few that scale linearly

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0How... do... you... know.... it ... is related to algorithms?

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1here, f(n) = log(n) represents how time scales as size increases for doing a 'particular job' using a 'particular algorithm'

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0I should have reworded 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
 11 months ago
Best ResponseYou've already chosen the best response.1given : t = log(n) the inverse wud be :n = 10^t

RolyPoly
 11 months ago
Best ResponseYou've already chosen the best response.0The 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
 11 months ago
Best ResponseYou've already chosen the best response.1general solution is to take inverse of time function

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1for our original probel : given : t = log(n) the general solution (inverse )wud be :n = 10^t units are in microseconds

ganeshie8
 11 months ago
Best ResponseYou've already chosen the best response.1this may enhance ur understanding on complexity analysis http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html
Ask your own question
Ask a QuestionFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.