What kind of crazy algorithm is that?

Computer Science Level 5

Agnishom developed a complicated algorithm for purposes unknown.

He then wanted to analyse it's time complexity. After a lot of complicated math, he came up with the following recurrence relation:

$T(n) = \Theta(n \text{lg}(n)) + \frac{1}{n} \sum_{k=2}^{n+1} k! T\left (\frac{n}{\sqrt{k!}} + \frac{\pi(n)}{\text{lg}^k(n)} \right)$

Unfortunately, he doesn't have time to solve this recurrence.

That's where you come in : Solve the above recurrence relation!

To which of the following sets does $T(n)$ belong to?

Notations:

\Theta(n^n)

\Theta(n^2)

\Theta(n \text{lg}^r (n))

for a suitable

r>1

\Theta(n)

\Theta(n \text{lg} (n))

\Theta(n^x \text{lg}^y (n))

for some suitable

x>1, y>1

\Theta(a^n)

for a suitable

a>1

1 solution

A Former Brilliant Member
Jul 25, 2016

We shall use the Akra-Bazzi Theorem as a heuristic tool.

Following the notations of the link, note that $p=2$ .

So, $T(x) \in \Theta \left( x^2 \left( 1+ \int_1^x \frac{\text{lg}(t)}{t^2} \, dt \right) \right)\\\implies T(n) \in \Theta(n^2)$

This can now be verified via the substitution method.

OMG, how did you know about that theorem?

Agnishom Chattopadhyay - 4 years, 10 months ago

CLRS. The whole statement was given at the end of the chapter. I later looked it up in Wikipedia.

Quite a neat theorem. Allows you to ignore floors and ceilings.

A Former Brilliant Member - 4 years, 10 months ago

Looks like you are going to rock the Algorithm Design and Analysis class

Agnishom Chattopadhyay - 4 years, 10 months ago

Thanks for letting us know about the Akra-Bazzi theorem.

From my understanding, the summation in this theorem is over a constant number of elements.

And $a_{i}$ should be constant.

Abdelhamid Saadi - 4 years, 5 months ago

Ah! Yes. The number of summands should've been constant.

But I just verified that the final result still holds.

I've edited my solution accordingly.

A Former Brilliant Member - 4 years, 5 months ago