Search code examples
algorithmdata-structuressubstitutionrecurrencemaster-theorem

Solve using either master theorem or by expansion

I have two questions, which I have trying but unable to figure them out. 1) 𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑛^4 2) 𝑇(𝑛) = 2𝑇 (𝑛/2) + 𝑛 lg 𝑛

For first one, I am assuming substitution (am I correct?), and got kb + T(n-k). Pretty sure that's wrong so need help with it.

For the second one, I have no idea at all...

Any help would be great! Thanks!

Solution

  • 1) So you got

    enter image description here

    ...? I don't know how you obtained this but it's certainly incorrect.

    This is basically the summation of the 4th power of all integers up to n. The standard formula for this is:

    enter image description here

    2) We can find a pattern if we keep expanding this:

    enter image description here

    The limit log n - 1 is because we keep dividing the parameter to T by 2, so the substitution as above can continue for log n lines until, say T(1) or wherever the stopping condition is. Continuing using the logarithm rules (google them if you don't know):

    enter image description here

    Both summations have log n terms. Since the 1st summation does not depend on i at all, we simply multiply by log n. The 2nd summation is given by a standard formula for summation of integers from 1 (or 0, doesn't matter in this case):

    enter image description here