A community for students.
Here's the question you clicked on:
 0 viewing
RolyPoly
 2 years 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?
RolyPoly
 2 years 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
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.0I am still not sure how to proceed..

ganeshie8
 2 years 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
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.010^6 us?? And why did you pick n = 10^(10^6)?

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

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

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

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

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

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

RolyPoly
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.1thats it, all bigOh problems are just primitive accounting problems lol

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

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

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

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

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

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

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

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

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

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

ganeshie8
 2 years 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
 2 years 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
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.1oops sorry, looks i was sounding bit offensive earlier

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

RolyPoly
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.1same is the case wid me, gimme a sec to digest ur equation

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

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

RolyPoly
 2 years 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
 2 years 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
 2 years 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
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.1still stuck on this ha ?

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

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

ganeshie8
 2 years 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
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.0\[\frac{n}{\log n}=\frac{N}{1,000,000}\]?

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

ganeshie8
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.0How do you know if it is the largest?

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

RolyPoly
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.1add 1 to that that, and plugin, wat do u get ?

ganeshie8
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.1but u want to complete job within 1s, so..

ganeshie8
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.1if it helps seeing this, let me plot the time Vs problemsize graph quick

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

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

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

ganeshie8
 2 years 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
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.1yup, if its linear then we can use ur proportion :)

ganeshie8
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.0How... do... you... know.... it ... is related to algorithms?

ganeshie8
 2 years 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
 2 years 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
 2 years ago
Best ResponseYou've already chosen the best response.1given : t = log(n) the inverse wud be :n = 10^t

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

ganeshie8
 2 years 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
 2 years 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
Sign UpFind 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.