Find Maximum n for Time Constraints: Solving Problems Using f(n) Microseconds

[evinda]

Hello! (Wave)

I am looking at the following exercise:
For each function $f(n)$ and for each time $t$ find the maximum size $n$ of the problem that can be solved in time $t$, assuming that the algorithm of the problem requires time $f(n)$ microseconds( 1 microsecond=$10^{-6}$ second)

Suppose that we have $f(n)=n!$ and want to fill the following array.

$$\begin{matrix}
\text{1 sec } & \text{1 min} & \text{1 hour } & \text{ 1 month } & \text{1 year} & \text{ 1 century} & \\
--- & --- & --- & --- & --- & --- &
\end{matrix}$$How can we find the desired values of $n$?

Do we have to use Stirling's approximation?Also we have to use the following relations, right? (Thinking)

• 1 sec=$10^6$ ms
• 1 minute=$60 \cdot 10^6$ ms
• 1 hour=$3600 \cdot 10^6$ ms
• 1 day=$24 \cdot 3600 \cdot 10^6$ ms
• 1 month=$30 \cdot 24 \cdot 3600 \cdot 10^6$ ms
• 1 year=$12 \cdot 30 \cdot 24 \cdot 3600 \cdot 10^6 $ ms
• 1 century=$100 \cdot 12 \cdot 30 \cdot 24 \cdot 3600 \cdot 10^6$ ms

 

[I like Serena]

Hello! (Wave)

I am looking at the following exercise:
For each function $f(n)$ and for each time $t$ find the maximum size $n$ of the problem that can be solved in time $t$, assuming that the algorithm of the problem requires time $f(n)$ microseconds( 1 microsecond=$10^{-6}$ second)

Suppose that we have $f(n)=n!$ and want to fill the following array.

$$\begin{matrix}
\text{1 sec } & \text{1 min} & \text{1 hour } & \text{ 1 month } & \text{1 year} & \text{ 1 century} & \\
--- & --- & --- & --- & --- & --- &
\end{matrix}$$How can we find the desired values of $n$?

Do we have to use Stirling's approximation?Also we have to use the following relations, right? (Thinking)

• 1 sec=$10^6$ ms
• 1 minute=$60 \cdot 10^6$ ms
• 1 hour=$3600 \cdot 10^6$ ms
• 1 day=$24 \cdot 3600 \cdot 10^6$ ms
• 1 month=$30 \cdot 24 \cdot 3600 \cdot 10^6$ ms
• 1 year=$12 \cdot 30 \cdot 24 \cdot 3600 \cdot 10^6 $ ms
• 1 century=$100 \cdot 12 \cdot 30 \cdot 24 \cdot 3600 \cdot 10^6$ ms

Hey! (Wave)

A year is 365.2425 days instead of 12x30=360 days. (Nerd)

I think that the easiest way to find the $n$ for $f(n)=n!$, is by simply iterating through $n$ and check when it reaches the required time.

For instance typing n! in Wolfram|Alpha gives us:
n! - Wolfram|Alpha Results
It shows $n!$ up to $n=10$.

From it we can tell that the maximum size $n$ that we can solve in 1 second is $n=9$. (Happy)

 

[evinda]

Hey! (Wave)

A year is 365.2425 days instead of 12x30=360 days. (Nerd)

A ok.. And how many days do we consider that a month has? (Thinking)

I think that the easiest way to find the $n$ for $f(n)=n!$, is by simply iterating through $n$ and check when it reaches the required time.

For instance typing n! in Wolfram|Alpha gives us:
n! - Wolfram|Alpha Results
It shows $n!$ up to $n=10$.

From it we can tell that the maximum size $n$ that we can solve in 1 second is $n=9$. (Happy)

A ok... (Nod)

 

[I like Serena]

A ok.. And how many days do we consider that a month has? (Thinking)

I think 30 days is fine for a month.
Of course the average duration of a month is 365.2425 / 12 = 30.3469 days. (Nerd)

 

[evinda]

I found this: http://clrs.skanev.com/01/problems/01.html

For $f(n)=\lg n$ at $1$ century, shouldn't it be $2^{365 \cdot 24 \cdot 36 \cdot 10^{10}}=2^{31536 \cdot 10^{11}}$ ?

Or am I wrong? (Thinking)

 

[I like Serena]

I found this: http://clrs.skanev.com/01/problems/01.html

For $f(n)=\lg n$ at $1$ century, shouldn't it be $2^{365 \cdot 24 \cdot 36 \cdot 10^{10}}=2^{31536 \cdot 10^{11}}$ ?

Or am I wrong? (Thinking)

He picked a different precision for a year.

He picked 365.24 days, accounting for leap years, and also for the non-leap year every century (and not accounting for the extra leap year every 4 centuries). (Wasntme)

He did pick 30 days for a month, and 365 days for a year.
So in each case he chose to round to the nearest number of days. (Smile)

 

[evinda]

He picked a different precision for a year.

He picked 365.24 days, accounting for leap years, and also for the non-leap year every century (and not accounting for the extra leap year every 4 centuries). (Wasntme)

He did pick 30 days for a month, and 365 days for a year.
So in each case he chose to round to the nearest number of days. (Smile)

So could we agnore the leap years? (Thinking)
If so, would it be then as follows?

$\begin{matrix}
& 1 \text{ century }\\
- & -\\ \\
\lg n & 2^{31536 \cdot 10^{11}}\\ \\
\sqrt{n} & 994519296 \cdot 10^{22}\\ \\
n & 31536 \cdot 10^{11}\\ \\
n \lg n & 68610956750\\ \\
n^2 & 56156922\\ \\
n^3 & 146645\\ \\
2^n & 51\\ \\
n! & 17
\end{matrix}$

 

[I like Serena]

So could we agnore the leap years? (Thinking)
If so, would it be then as follows?

$\begin{matrix}
& 1 \text{ century }\\
- & -\\ \\
\lg n & 2^{31536 \cdot 10^{11}}\\ \\
\sqrt{n} & 994519296 \cdot 10^{22}\\ \\
n & 31536 \cdot 10^{11}\\ \\
n \lg n & 68610956750\\ \\
n^2 & 56156922\\ \\
n^3 & 146645\\ \\
2^n & 51\\ \\
n! & 17
\end{matrix}$

Looks as if you have almost the same numbers as the web page you referred to.
So yes, I believe this is correct. (Smile)

I would write down that you consider a century to be 100 years of 365 days each.
This is a couple of days off, but I'm pretty sure that is not relevant for the problem. (Nerd)

 

[evinda]

Looks as if you have almost the same numbers as the web page you referred to.
So yes, I believe this is correct. (Smile)

When we consider $f(n)=n \lg n$, how do we come to the number [m]68610956750[/m]?
Is it right? Because at the year, I found for $f(n)=n \cdot \lg n$ the result [m]797633893349[/m] which is bigger...

I would write down that you consider a century to be 100 years of 365 days each.
This is a couple of days off, but I'm pretty sure that is not relevant for the problem. (Nerd)

A ok... (Smile)

 

[I like Serena]

When we consider $f(n)=n \lg n$, how do we come to the number [m]68610956750[/m]?
Is it right? Because at the year, I found for $f(n)=n \cdot \lg n$ the result [m]797633893349[/m] which is bigger...

Where is that number?
In the web page I see 797633893349, which is also what Wolfram|Alpha finds for me. (Wasntme)

 

[Nono713]

Not sure how you found your number, but the page you linked is just using the base-2 logarithm which is what $\mathrm{lg}$ commonly refers to (together with the leap year conventions and stuff)

> NSolve[n Log[2, n] == 365 * 24 * 3600 * 10^6, {n}]

{{n -> 7.97634*10^11}}

 

[evinda]

Where is that number?
In the web page I see 797633893349, which is also what Wolfram|Alpha finds for me. (Wasntme)

Not sure how you found your number, but the page you linked is just using the base-2 logarithm which is what $\mathrm{lg}$ commonly refers to (together with the leap year conventions and stuff)

> NSolve[n Log[2, n] == 365 * 24 * 3600 * 10^6, {n}]

{{n -> 7.97634*10^11}}

I also used Wolfram and I found this:
n'*'log_2n'='100'*'365'*'24'*'3600'*'10'^'6 - Wolfram|Alphae'^''('ProductLog'('3153600000000000 log'('2')'')'')' - Wolfram|Alpha

 

[Nono713]

Since when is 100*365*24*3600*10^6 a year? I think you got mixed up with centuries here... ;)

 

[evinda]

Since when is 100*365*24*3600*10^6 a year? I think you got mixed up with centuries here... ;)

I was talking about the case [m] t=1 century [/m].

 

[Nono713]

I was talking about the case [m] t=1 century [/m].

Oh, okay, I must have misunderstood the last few posts then..

 

[evinda]

How could I explain how we fill the table? (Thinking)