## 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? 7 months ago 7 months ago

1. whereismymind49 Group Title

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

2. RolyPoly Group Title

I am still not sure how to proceed..

3. ganeshie8 Group Title

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

4. ganeshie8 Group Title

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

5. RolyPoly Group Title

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

6. ganeshie8 Group Title

i just guessed, u can setup an equation aswell

7. ganeshie8 Group Title

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

8. ganeshie8 Group Title

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

9. ganeshie8 Group Title

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

10. ganeshie8 Group Title

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

11. ganeshie8 Group Title

remember that 10^6us = 1s

12. ganeshie8 Group Title

us = micro second

13. RolyPoly Group Title

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

14. ganeshie8 Group Title

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

15. RolyPoly Group Title

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

16. ganeshie8 Group Title

did u get the phrase 'size of problem' ?

17. RolyPoly Group Title

No, not at all.

18. ganeshie8 Group Title

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

19. ganeshie8 Group Title

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

20. ganeshie8 Group Title

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

21. ganeshie8 Group Title

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 Group Title

here problem size is 1000000

23. ganeshie8 Group Title

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

24. ganeshie8 Group Title

see if that seems plausible

25. RolyPoly Group Title

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

26. ganeshie8 Group Title

dint get u ?

27. RolyPoly Group Title

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 Group Title

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

29. ganeshie8 Group Title

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

30. ganeshie8 Group Title

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 Group Title

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

32. ganeshie8 Group Title

yes ur right

33. RolyPoly Group Title

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 Group Title

oops sorry, looks i was sounding bit offensive earlier

35. RolyPoly Group Title

It's ok...

36. ganeshie8 Group Title

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

37. RolyPoly Group Title

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

38. ganeshie8 Group Title

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

39. ganeshie8 Group Title

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

40. ganeshie8 Group Title

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

41. RolyPoly Group Title

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 Group Title

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

43. ganeshie8 Group Title

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 Group Title

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

45. ganeshie8 Group Title

still stuck on this ha ?

46. RolyPoly Group Title

Yes...

47. ganeshie8 Group Title

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

48. ganeshie8 Group Title

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 Group Title

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

50. RolyPoly Group Title

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 Group Title

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

52. ganeshie8 Group Title

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

53. ganeshie8 Group Title

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

54. RolyPoly Group Title

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

55. ganeshie8 Group Title

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

56. ganeshie8 Group Title

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

57. RolyPoly Group Title

How do you know if it is the largest?

58. ganeshie8 Group Title

plugin that number in the given function

59. RolyPoly Group Title

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

60. ganeshie8 Group Title

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

61. ganeshie8 Group Title

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

62. ganeshie8 Group Title

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

63. RolyPoly Group Title

Ah! Ok...

64. ganeshie8 Group Title

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

65. ganeshie8 Group Title

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

66. ganeshie8 Group Title

|dw:1389594869323:dw|

67. ganeshie8 Group Title

|dw:1389594972424:dw|

68. ganeshie8 Group Title

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

69. ganeshie8 Group Title

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

70. RolyPoly Group Title

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

71. ganeshie8 Group Title

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

72. ganeshie8 Group Title

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

73. RolyPoly Group Title

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

74. ganeshie8 Group Title

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

75. RolyPoly Group Title

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 Group Title

dint get u

77. ganeshie8 Group Title

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

78. RolyPoly Group Title

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 Group Title

general solution is to take inverse of time function

80. ganeshie8 Group Title

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

81. ganeshie8 Group Title

*problem

82. ganeshie8 Group Title

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