## RolyPoly one year 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?

1. whereismymind49

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

2. RolyPoly

I am still not sure how to proceed..

3. ganeshie8

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

4. ganeshie8

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

5. RolyPoly

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

6. ganeshie8

i just guessed, u can setup an equation aswell

7. ganeshie8

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

8. ganeshie8

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

9. ganeshie8

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

10. ganeshie8

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

11. ganeshie8

remember that 10^6us = 1s

12. ganeshie8

us = micro second

13. RolyPoly

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

14. ganeshie8

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

15. RolyPoly

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

16. ganeshie8

did u get the phrase 'size of problem' ?

17. RolyPoly

No, not at all.

18. ganeshie8

okay, suppose i give u $$10$$ different numbers and ask you to sort them

19. ganeshie8

we say, the size of this problem is $$10$$

20. ganeshie8

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

21. ganeshie8

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

here problem size is 1000000

23. ganeshie8

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

24. ganeshie8

see if that seems plausible

25. RolyPoly

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

26. ganeshie8

dint get u ?

27. RolyPoly

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

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

29. ganeshie8

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

30. ganeshie8

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

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

32. ganeshie8

yes ur right

33. RolyPoly

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

oops sorry, looks i was sounding bit offensive earlier

35. RolyPoly

It's ok...

36. ganeshie8

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

37. RolyPoly

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

38. ganeshie8

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

39. ganeshie8

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

40. ganeshie8

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

41. RolyPoly

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

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

43. ganeshie8

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

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

45. ganeshie8

still stuck on this ha ?

46. RolyPoly

Yes...

47. ganeshie8

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

48. ganeshie8

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

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

50. RolyPoly

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

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

52. ganeshie8

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

53. ganeshie8

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

54. RolyPoly

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

55. ganeshie8

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

56. ganeshie8

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

57. RolyPoly

How do you know if it is the largest?

58. ganeshie8

plugin that number in the given function

59. RolyPoly

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

60. ganeshie8

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

61. ganeshie8

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

62. ganeshie8

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

63. RolyPoly

Ah! Ok...

64. ganeshie8

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

65. ganeshie8

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

66. ganeshie8

|dw:1389594869323:dw|

67. ganeshie8

|dw:1389594972424:dw|

68. ganeshie8

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

69. ganeshie8

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

70. RolyPoly

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

71. ganeshie8

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

72. ganeshie8

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

73. RolyPoly

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

74. ganeshie8

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

75. RolyPoly

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

dint get u

77. ganeshie8

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

78. RolyPoly

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

general solution is to take inverse of time function

80. ganeshie8

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

81. ganeshie8

*problem

82. ganeshie8

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