Search code examples
algorithmtime-complexityasymptotic-complexityupperbound

Asymptotic Upper Bound

Hi I solved a question with recursion tree method. Then I reached the below equatition. n ∑ 3^(i-1)(n - (i - 1)) i=1

I need to find asymptotic upper bound for that equation. Any help would be appreciated.

Solution

  • Wolfram Alpha is a great tool for this: https://www.wolframalpha.com/input/?i=sum(3%5E(i-1)(n+-+i+%2B+1)+for+i+%3D+1..n)

    That tool simplifies the sum to: (-2n + 3^(n+1) - 3)/4.

    In terms of big-O, that's O(3^n).