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?


  • \(\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...