I'm watching this computer science video on computational time complexity of a function where they introduce some maths and it doesn't make sense to me. I'm not even sure what the name for this maths is so I apologise for that.
Basically they start with the the function T(n) as defined on line 1 and on line 2 it's given that t(0) = 1:
1 T(n) = T(n-1) + 3 if n > 0
2 T(0) = 1
Then they say that the above expression can be reduced as:
3 T(n) = T(n-1) + 3
4 = T(n-2) + 6
5 = T(n-3) + 9
6 = T(n-k) + 3k
The "reduction" part is which I don't understand - lines 3 to 5. They say "t(n-1) can be written as T(n-2) + 3 so overall the expression will be T(n-2) + 6". That is what I don't get.
So, from the above, why can line 3 be written as it is on line 4? And then again why can line 4 can be written as it is on line 5. They seem to be applying some trivial rules that I can't remember from high school.
Any explanation as to what they are doing is welcome. Also, links to where I can learn/practice more of this type of problem would be great.
Essentially they just keep applying the first rule over and over.
Since $T(n)=T(n-1)+3$ for $n>0$ then if you want to rewrite $T(n-1)$ you just think of $n-1$ as being your $n$. It might be easier to see if we work with $T(k-1)$ then if you call $k-1=n$ then you have $T(k-1)=T(n)=T(n-1)+3=T((k-1)-1)+3$ where we just plug in for $n=k-1$. The same approach using iterations on $n$ gives $T(n-1)=T((n-1)-1)+3=T(n-2)+3=(T((n-2)-1)+3)+3=T(n-3)+6$.
The essential bit is that we say $T(n)=T(n-1)+3$ for all $n>0$. It might be even easier to see with some actual numbers.
If you have $T(5)=T(5-1)+3=T(4)+3=(T(4-1)+3)+3=T(3)+6$.
Does that explain it?