# What kind of crazy algorithm is that?

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:

• $$\text{lg}(n)$$ denotes $$\log_2(n)$$.
• $$\text{lg}^k(n)$$ denotes $$(\log_2(n))^k$$.
• $$\pi(n)$$ denotes the prime counting function.
• $$k!$$ denotes the factorial function.
×