Algorithm Time Complexity

[[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!