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.

×

Problem Loading...

Note Loading...

Set Loading...