Question

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?

Answer 1

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

Answer 2

I am still not sure how to proceed..

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

i just guessed, u can setup an equation aswell

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

below eq'n :-

10^6 us = log(n)

Answer 11

remember that 10^6us = 1s

Answer 12

us = micro second

Answer 13

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

Answer 14

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

Answer 15

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

Answer 16

did u get the phrase 'size of problem' ?

Answer 17

No, not at all.

Answer 18

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

Answer 19

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

Answer 20

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

Answer 21

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.

Answer 22

here problem size is 1000000

Answer 23

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

Answer 24

see if that seems plausible

Answer 25

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

Answer 26

dint get u ?

Answer 27

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

Answer 28

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

Answer 29

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

Answer 30

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

Answer 31

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

Answer 32

yes ur right

Answer 33

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?

Answer 34

oops sorry, looks i was sounding bit offensive earlier

Answer 35

It's ok...

Answer 36

10^6 us = log(n)

whats the problem wid this equation ?

Answer 37

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

Answer 38

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

Answer 39

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

Answer 40

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

Answer 41

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

Answer 42

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

Answer 43

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

Answer 44

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

Answer 45

still stuck on this ha ?

Answer 46

Yes...

Answer 47

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

Answer 48

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

Answer 49

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

Answer 50

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

Answer 51

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

Answer 52

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

Answer 53

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

Answer 54

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

Answer 55

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

Answer 56

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

Answer 57

How do you know if it is the largest?

Answer 58

plugin that number in the given function

Answer 59

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

Answer 60

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

Answer 61

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

Answer 62

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

Answer 63

Ah! Ok...

Answer 64

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

Answer 65

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