# Thread: Big Oh vs Theta - Need clarification

1. ## Big Oh vs Theta - Need clarification

Hi,

I'm reading a paper at the moment. In the paper they evaluate the best and worse length of time it takes for a system to become consistent (i.e. all pointers in system are correct). The worst case is t = N.tInt where tInt is a time interval and N is the number of nodes in the system. The best case if t = (N-1).tInt.

The paper then goes on to say the upper bound on the time complexity is O(N). This I think I understand. Now here's the problem: The paper then says that because the upper and lower bound is O(N) there is a tight bound of Theta (N) on the time complexity.

I would have thought that the lower bound would be O(N-1) and not O(N)?And really given that I'm referring to the lower bound the O would be referring to Omega and not Big Oh notation. If thats the case, then Theta(N) wouldn't be true because as I understand it, theta applies when both Big Oh and Omega are the same.

2. $\displaystyle O(n-1) \text{ is } O(n)$

CB

3. Hi Captain Black,

Can you explain why that is? Maybe I'm not fully understanding the significance of the Big Oh notation. I would have thought that if the worst case time complexity of a system is O(N) with N equal to 40 - then the worst case time complexity would be 40 * time intervals. The best case is O(N-1) so that would be 39 * time intervals - not the same...

Big-O notation has nothing to do with specific values of $\displaystyle \displaystyle n$, but is an asymptotic property. Because $\displaystyle \displaystyle \lim_{n \to \infty}\dfrac{n}{n-1}=1$ we have $\displaystyle O(n)=O(n-1)$. That is for all $\displaystyle \displaystyle f(n) \in O(n-1)$ we have $\displaystyle \displaystyle f(n) \in O(n)$ and vice-versa