Search code examples
recursiontime-complexitycombinatoricsgamma-function

Time complexicity of recursive function

I have a recursive function f(n) with time complexicity

O(f(n)) = O(combination(n, n/2) * f(n/2)^2)

where combination(a, b) means combination nuber a above b.

I tried to simplify it, but don't have enough mathematical skills. The only thing that I foud out is that

combination(n,n/2) = 2^n * (gamma(n/2 + 1/2)/(sqrt(1/2) * gamma(n/2 + 1)))

Solution

  • I have allready solved it in this thread on satck exchange:

    https://math.stackexchange.com/questions/2642848/time-complexicity-of-recursive-function?noredirect=1#comment5458208_2642848