Here's the question you clicked on:

55 members online
  • 0 replying
  • 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?

  • This Question is Closed
  1. whereismymind49
    • 2 years ago
    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

  2. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I am still not sure how to proceed..

  3. ganeshie8
    • 2 years ago
    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

  4. ganeshie8
    • 2 years ago
    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}\)

  5. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  6. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    i just guessed, u can setup an equation aswell

  7. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  8. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  9. ganeshie8
    • 2 years ago
    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. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  11. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    remember that 10^6us = 1s

  12. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    us = micro second

  13. RolyPoly
    • 2 years ago
    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) ?

  14. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  15. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  16. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    did u get the phrase 'size of problem' ?

  17. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    No, not at all.

  18. ganeshie8
    • 2 years ago
    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

  19. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  20. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  21. ganeshie8
    • 2 years ago
    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.

  22. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    here problem size is 1000000

  23. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  24. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    see if that seems plausible

  25. RolyPoly
    • 2 years ago
    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}}\]

  26. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    dint get u ?

  27. RolyPoly
    • 2 years ago
    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}\]

  28. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  29. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  30. ganeshie8
    • 2 years ago
    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 :|

  31. RolyPoly
    • 2 years ago
    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?

  32. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    yes ur right

  33. RolyPoly
    • 2 years ago
    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?

  34. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    oops sorry, looks i was sounding bit offensive earlier

  35. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    It's ok...

  36. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  37. RolyPoly
    • 2 years ago
    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.

  38. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  39. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  40. ganeshie8
    • 2 years ago
    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

  41. RolyPoly
    • 2 years ago
    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..

  42. ganeshie8
    • 2 years ago
    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 :)

  43. ganeshie8
    • 2 years ago
    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

  44. RolyPoly
    • 2 years ago
    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.

  45. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    still stuck on this ha ?

  46. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yes...

  47. ganeshie8
    • 2 years ago
    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 ?

  48. ganeshie8
    • 2 years ago
    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

  49. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  50. RolyPoly
    • 2 years ago
    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}\]

  51. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  52. ganeshie8
    • 2 years ago
    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 ?

  53. ganeshie8
    • 2 years ago
    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

  54. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  55. ganeshie8
    • 2 years ago
    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

  56. ganeshie8
    • 2 years ago
    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 ?

  57. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    How do you know if it is the largest?

  58. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    plugin that number in the given function

  59. RolyPoly
    • 2 years ago
    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?

  60. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  61. ganeshie8
    • 2 years ago
    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

  62. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  63. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ah! Ok...

  64. ganeshie8
    • 2 years ago
    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.

  65. ganeshie8
    • 2 years ago
    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

  66. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1389594869323:dw|

  67. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1389594972424:dw|

  68. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  69. ganeshie8
    • 2 years ago
    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

  70. RolyPoly
    • 2 years ago
    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|

  71. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  72. ganeshie8
    • 2 years ago
    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

  73. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  74. ganeshie8
    • 2 years ago
    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'

  75. RolyPoly
    • 2 years ago
    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?

  76. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    dint get u

  77. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  78. RolyPoly
    • 2 years ago
    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 ?

  79. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    general solution is to take inverse of time function

  80. ganeshie8
    • 2 years ago
    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

  81. ganeshie8
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    *problem

  82. ganeshie8
    • 2 years ago
    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

  83. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy