difficult asymptotic(recurrence) function (algorithm analysis)

Question

i am stuck on this one and i don't know how to solve it, no matter what i try i just can't find a way to play with the function so i can represent it in a way that will allow me to find a g(n), so that g(n) is T(n)∈Θ(g(n))

the function i am having trouble with is:

$T(n)=4n^4T(\sqrt n) +(n^6lgn+3lg^7n)(2n^2lgn+lg^3n)$

additionally, if you can - could you please check if i am on the right path with:

$T(n)=T(n-1)+\frac{1}{n}+\frac{1}{n^2}$

to solve it i tried to use: $T(n)-T(n-1)=\frac{1}{n}+\frac{1}{n^2}$ iff $(T(n)-T(n-1))+(T(n-1)-T(n-2))+\ldots+(T(2)-T(1))=\frac{1}{n}+\frac{1}{n-1}+...+\frac{1}{n^2}+\frac{1}{\left(n-1\right)^2}+....$ iff $(T(n)-T(n-1))+(T(n-1)-T(n-2))+\ldots+(T(2)-T(1))=T(n)=T(1)+\sum_{k=2}^n\frac{1}{n}+\sum_{k=2}^n\frac{1}{n^2}$ and then using the harmonic series formula. however i don't know how to continue and finish it and find the asymptotic boundaries to solve it

i hope that on the second i am on the right path. however i don't know how to solve the first one at all. if i've done any mistakes, please show me the right way so i can improve my mistakes.

thank you very much for your help

sorry that for some reason math doesn't show correctly here

Answer 1

Following on from the comments:

---

Solving (2) first since it is more straightforward.

Your expansion attempt is correct. Writing it slightly differently:

• A, harmonic series - asymptotically equal to the natural logarithm:

  

  γ = 0.57721... is the Euler-Mascheroni constant.

• B, sum of inverse squares - the infinite sum is the famous Basel problem:

  

  Which is 1.6449.... Therefore since B is monotonically increasing, it will always be O(1).

The total complexity of (2) is simply Θ(log n).

---

(1) is a little more tedious.

• Little-o notation: strictly lower complexity class, i.e.:

  

• Assume a set of N functions {F_i} is ordered in decreasing order of complexity, i.e. F2 = o(F1) etc. Take a linear combination of them:

  

  Thus a sum of different functions is asymptotically equal to the one with the highest growth rate.

• To sort the terms in the expansion of the two parentheses, note that

  

  Provable by applying L'Hopital's rule. So the only asymptotically significant term is n^6 log n * 2n^2 log n = 2n^8 log^2 n.

• Expand the summation as before, note that i) the factor 4n^4 accumulates, ii) the parameter for the m-th expansion is n^(1/(2^m)) (repeated square-root).

  The new term added by the m-th expansion is therefore (will assume you know how to do this since you were able to do the same for (2)):

  

  Rather surprisingly, each added term is precisely equal to the first.

• Assume that the stopping condition for recursive expansion is n < 2 (which of course rounds down to T(1)):

  

  Since each added term t_m is always the same, simply multiply by the maximum number of expansions:

Function (1) is