Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

RolyPoly Group Title

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?

  • 10 months ago
  • 10 months ago

  • This Question is Closed
  1. whereismymind49 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    So you want the value that will make lg(n) = 1 second or 1000000 microsecond

    • 10 months ago
  2. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I am still not sure how to proceed..

    • 10 months ago
  3. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    say n = 10^(10^6) then u wil get f(10^(10^6)) = log(10^(10^6)) us = 10^6 us = 1s

    • 10 months ago
  4. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    so the largest size of problem that can be solved in 1s is \(10^{1000000}\)

    • 10 months ago
  5. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    10^6 us?? And why did you pick n = 10^(10^6)?

    • 10 months ago
  6. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    i just guessed, u can setup an equation aswell

    • 10 months ago
  7. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    we're given :- time required to solve the problem takes f(n) microseconds

    • 10 months ago
  8. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    so, if the problem size is n, then it takes f(n) microseconds

    • 10 months ago
  9. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    you need to solve the value of n, that makes f(n) = 1s

    • 10 months ago
  10. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    below eq'n :- 10^6 us = log(n)

    • 10 months ago
  11. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    remember that 10^6us = 1s

    • 10 months ago
  12. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    us = micro second

    • 10 months ago
  13. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Ah! So, if it is one minute instead of one second, then it will be 60 x 10^6 us = lg(n) ?

    • 10 months ago
  14. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    thats it, all bigOh problems are just primitive accounting problems lol

    • 10 months ago
  15. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Accounting is way easier than this. I just can't comprehend the problem. :(

    • 10 months ago
  16. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    did u get the phrase 'size of problem' ?

    • 10 months ago
  17. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    No, not at all.

    • 10 months ago
  18. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    okay, suppose i give u \(10\) different numbers and ask you to sort them

    • 10 months ago
  19. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    we say, the size of this problem is \(10\)

    • 10 months ago
  20. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    and lets say, u take 1 minute to solve them.

    • 10 months ago
  21. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

    • 10 months ago
  22. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    here problem size is 1000000

    • 10 months ago
  23. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    'problem size' and 'data size' both refer to same thing.

    • 10 months ago
  24. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    see if that seems plausible

    • 10 months ago
  25. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Ugh! Why is it not this: \[\frac{\lg n}{1}=\frac{1}{\lg n \times 10^{-6}}\]

    • 10 months ago
  26. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    dint get u ?

    • 10 months ago
  27. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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}\]

    • 10 months ago
  28. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    n = 1 is undefined i guess, cuz it wud make the time 0

    • 10 months ago
  29. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    consider the cases n > 1, and use bit common sense

    • 10 months ago
  30. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • 10 months ago
  31. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    " required to solve the problem takes f(n) microseconds" Isn't it lg(n) us instead of 1 us?

    • 10 months ago
  32. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    yes ur right

    • 10 months ago
  33. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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?

    • 10 months ago
  34. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    oops sorry, looks i was sounding bit offensive earlier

    • 10 months ago
  35. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    It's ok...

    • 10 months ago
  36. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    10^6 us = log(n) whats the problem wid this equation ?

    • 10 months ago
  37. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I don't understand how you get this equation, and I don't understand why mine is not correct.

    • 10 months ago
  38. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    same is the case wid me, gimme a sec to digest ur equation

    • 10 months ago
  39. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    wid ur equaiton, wats the largest size you're getting ?

    • 10 months ago
  40. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    we may plug that number in reverse and see if it works or not

    • 10 months ago
  41. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 10 months ago
  42. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    humm ok, ima have dinner... wil get back and have a look at this again :)

    • 10 months ago
  43. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    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

    • 10 months ago
  44. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    \[\frac{n}{\lg n \times 10^{-6}} = \frac{N}{1}\] N = Number of things done in one second.

    • 10 months ago
  45. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    still stuck on this ha ?

    • 10 months ago
  46. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Yes...

    • 10 months ago
  47. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    okay, i tried but im not getting ur equation, wat u trying to do wid that equation can u explain ?

    • 10 months ago
  48. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    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

    • 10 months ago
  49. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    that gives the 'n' value corresponding to 10^6 us

    • 10 months ago
  50. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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}\]

    • 10 months ago
  51. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    thats right, wat if it takes log(n) dollars to buy n chocolates ?

    • 10 months ago
  52. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    and you're asked to find how many u can buy wid a million dollars money ?

    • 10 months ago
  53. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    the price per chocolate is not fixed here, clearly it depends on how many u buy

    • 10 months ago
  54. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    \[\frac{n}{\log n}=\frac{N}{1,000,000}\]?

    • 10 months ago
  55. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    its not a linear scaling, i dont think you can do it that way

    • 10 months ago
  56. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    first tell me this, are u convinced 10^(10^6) is the largest problem size yet ?

    • 10 months ago
  57. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    How do you know if it is the largest?

    • 10 months ago
  58. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    plugin that number in the given function

    • 10 months ago
  59. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    It works, but that does not guarantee there is no other (larger) solution, does it?

    • 10 months ago
  60. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    add 1 to that that, and plugin, wat do u get ?

    • 10 months ago
  61. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    u will get 1s + for any value larger than 10^(10^6) cuz log(n) is a strictly increasing function

    • 10 months ago
  62. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    but u want to complete job within 1s, so..

    • 10 months ago
  63. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Ah! Ok...

    • 10 months ago
  64. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    the question is begging us to solve f(n) = log(n) = 10^6 no more than that.

    • 10 months ago
  65. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    if it helps seeing this, let me plot the time Vs problem-size graph quick

    • 10 months ago
  66. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1389594869323:dw|

    • 10 months ago
  67. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1389594972424:dw|

    • 10 months ago
  68. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    time to complete the job, depends on teh size of job

    • 10 months ago
  69. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    so ive put time in y-axis and size in x-axis. see if that makes more/less sense

    • 10 months ago
  70. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    It makes more sense :) Let say, if f(n) = n, will the graph then be |dw:1389595232578:dw|

    • 10 months ago
  71. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    yup, if its linear then we can use ur proportion :)

    • 10 months ago
  72. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    however most algorithms we deal with are exponential/logarthmic/polynomial there will be very few that scale linearly

    • 10 months ago
  73. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    How... do... you... know.... it ... is related to algorithms?

    • 10 months ago
  74. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    here, f(n) = log(n) represents how time scales as size increases for doing a 'particular job' using a 'particular algorithm'

    • 10 months ago
  75. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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?

    • 10 months ago
  76. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    dint get u

    • 10 months ago
  77. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    given : t = log(n) the inverse wud be :n = 10^t

    • 10 months ago
  78. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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 ?

    • 10 months ago
  79. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    general solution is to take inverse of time function

    • 10 months ago
  80. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    for our original probel :- given : t = log(n) the general solution (inverse )wud be :n = 10^t units are in microseconds

    • 10 months ago
  81. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    *problem

    • 10 months ago
  82. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    this may enhance ur understanding on complexity analysis http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html

    • 10 months ago
    • Attachments:

See more questions >>>

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

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.