Hey guys, I have 2 problems I couldn't answer in my readings and was wondering if i could get some help:

1) Consider the problem, of computing N!=1*2*...*N. If N is an n-bit number, how many bits long is N! approximately, in Θ(. ) notation? Give an algorithm to compute N! and analyze its running time.

P.s. Θ is theta

2) So I know that the linear-time median find algorithm; groups the elements of the set for which the median is to be found into groups of 5:

the question asks how I would Analyze the running time of the algorithm if the groups were made of 7 elements instead of 5?

Thanks guys,

-Bash

## computing and linear time median find algorithm

### Re: computing and linear time median find algorithm

One approximation for n! is the stirling formula:

n! ~ Sqrt(2*pi*n)*(n/e)^n

Counting digits is some kind of Log10 so:

Log10(Sqrt(2*pi*n)*(n/e)^n) = 1/2 * Log10(2*pi*n) + n* Log10(n/e)

Θ(C1 + 1/2*Log10(N) + N * Log10(N) - N*C2) = Θ(N*log(N)) = Θ(e^n * n)

For this issue you may use a fast multiplication like Schönhage-Strassen or Karazuba with Θ(m*log(m)*log(log(m))) for m-bit operands

Multiply by N-1 multiplications with at maximum m=Θ(N*log(N)) bit. (increasing during each multiplication)

--> Θ(N*N*log(N)*log(log(N)))

n! ~ Sqrt(2*pi*n)*(n/e)^n

Counting digits is some kind of Log10 so:

Log10(Sqrt(2*pi*n)*(n/e)^n) = 1/2 * Log10(2*pi*n) + n* Log10(n/e)

Θ(C1 + 1/2*Log10(N) + N * Log10(N) - N*C2) = Θ(N*log(N)) = Θ(e^n * n)

For this issue you may use a fast multiplication like Schönhage-Strassen or Karazuba with Θ(m*log(m)*log(log(m))) for m-bit operands

Multiply by N-1 multiplications with at maximum m=Θ(N*log(N)) bit. (increasing during each multiplication)

--> Θ(N*N*log(N)*log(log(N)))