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?
2
votes
An O(whatever) computation can specify a minimum value of n for which the performance bound holds. Thus, there's no problem of predicting impossibly low times for degenerate cases, such as trying to perform an NlgN sort when N is 1 (but lgN is zero).
- supercat
Also the Big-O is about the limit for the behaviour of an algorithm as the number approaches infinity. Infinity = infinity -1 = infinity/2 so O(n) = O(n-1) = O(n/2) But the master theorem is about how to make a recurrence relation for the amount of work done by an algorithm - it has nothing to do with a limit approaching infinity so you can't use the simplifications that infinity allows.
- Jerry Jeremiah
Ohh that makes so much sense. Thanks!
- dawooshifingerhold
1 Answers
2
votes
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!
