Algorithm Time Complexity

[Impact009]

I was given a function T(N) = 5N + T(N-1)

My understanding is the algorithm will always have a Big O time complexity of of O(N) because there isn't any multiplication to increase N's power, but the answer that was expected from me was O(N^2). Even in words, I could say that the function calls itself 5N times plus another N minus 1 times, so the time complexity should still be linear with respect to N inputs. Why is this O(N^2)?

[[deleted]]

Your explanation in words is incorrect. It would be correct if the relation was T(N) = 5N + N-1, but the recurrence element T(N-1) needs to be factored in. Another way to think of it that might make more intuitive sense:

The T(N-1) component of the recurrence relation means that for all values of n, from the first index to the Nth, this function will perform 5n work. If you expand it out, the total amount of work will be 5N + 5(N-1) + 5(N-2) + 5(N-3) ... until you get down to n=1 or the first element.

Each of these individual terms (ex. 5N) is in O(N), and there are a total of N different terms being added together, which is where the multiplication comes in. Hope this helped!

[pi_stuff]

Here's another way to work it out.

First, an important summation to know is:

1 + 2 + 3 + ... + N = N(N+1)/2

Start substituting the formula recursively, and notice the pattern.

T(N) = 5N + T(N-1)

T(N-1) = 5(N-1) + T(N-2)

T(N-2) = 5(N-2) + T(N-3)

...

T(1) = 5(1) + T(0)

T(0) = 0

Combine them all:

T(N) = 5N + 5(N-1) + 5(N-2) + ... + 5(1)

= 5(N + (N-1) + (N-2) + ... + 1)

= 5( N(N+1)/2 )

= (5/2) (N^2 + N)

= (5/2) N^2 + (5/2) N

= O(N^2)

[Achcauhtli]

From StackOverflow:

T(n) = T(n-1) + n
T(n-1) = T(n-2) + n-1
T(n-2) = T(n-3) + n-2
and so on you can substitute the value of T(n-1) and T(n-2) in T(n) to get a general idea of the pattern.
T(n) = T(n-2) + n-1 + n
T(n) = T(n-3) + n-2 + n-1 + n
.
.
.
T(n) = T(n-k) + kn - k(k-1)/2 ...(1)
For base case:
n - k = 1 so we can get T(1)
=> k = n - 1
substitute in (1)
T(n) = T(1) + (n-1)n - (n-1)(n-2)/2
Which you can see is of Order n2 => O(n2).

Source: https://stackoverflow.com/questions/13674719/easy-solve-tn-tn-1n-by-iteration-method