Thread: 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.

CB

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...

Thanks in advance

Originally Posted by kerrymaid

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...

Thanks in advance

Big-O notation has nothing to do with specific values of , but is an asymptotic property. Because we have . That is for all we have and vice-versa

CB