Page 1 of 1

computing and linear time median find algorithm

Posted: Wed Jan 28, 2015 8:23 pm
by bash
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

Re: computing and linear time median find algorithm

Posted: Wed Jan 28, 2015 11:41 pm
by v6ph1
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)))