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.