computing and linear time median find algorithm

Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
Post Reply
bash
Posts: 1
Joined: Wed Jan 28, 2015 8:20 pm

computing and linear time median find algorithm

Post by bash » Wed Jan 28, 2015 8:23 pm

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

v6ph1
Posts: 118
Joined: Mon Aug 25, 2014 6:14 pm

Re: computing and linear time median find algorithm

Post by v6ph1 » Wed Jan 28, 2015 11:41 pm

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)))
Image

Post Reply