Ok So I'm pretty new to CS and was recently learning about Big-O, Theta, and Omega as well as the master theorem and in lecture I saw that this was not the case for some reason and was wondering why is that?
Although both O(n) and T(n) use capital letters on the outside and lower-case n in the middle, they represent fundamentally different concepts.
If you’re analyzing an algorithm using a recurrence relation, it’s common to let T(n) denote the amount of time it takes for the algorithm to complete on an input of size n. As a result, we wouldn’t expect T(n) to be the same as T(n-1), since, in most cases, algorithms take longer to run when you give them larger inputs.
More generally, for any function f, if you wanted to claim that f(n) = f(n-1), you’d need to explain why you could assume this because this generally isn’t the case.
The tricky bit here is that when we write O(n), it looks like we’re writing a function named O and passing in the argument n, but the notation means something totally different. The notation O(n) is a placeholder for “some function that, when the inputs gets really big, is bounded from above by a multiple of n.” Similarly, O(n-1) means “some function that, when the inputs get really big, is bounded from above by a multiple of n-1.” And it happens to be the case that any function that’s bounded above by a multiple of n is also bounded from above by a multiple of n-1, which is why O(n) and O(n-1) denote the same thing.
Hope this helps!