Results 1 to 4 of 4

Math Help - Big Oh vs Theta - Need clarification

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    42

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    O(n-1)  \text{ is } O(n)

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2009
    Posts
    42
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by kerrymaid View Post
    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 \displaystyle n, but is an asymptotic property. Because \displaystyle \lim_{n \to \infty}\dfrac{n}{n-1}=1 we have O(n)=O(n-1). That is for all \displaystyle f(n) \in O(n-1) we have \displaystyle f(n) \in O(n) and vice-versa

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: July 8th 2010, 03:13 PM
  2. Replies: 0
    Last Post: April 29th 2010, 10:24 AM
  3. Replies: 2
    Last Post: March 29th 2010, 07:38 AM
  4. Replies: 3
    Last Post: February 6th 2009, 04:19 PM
  5. Replies: 1
    Last Post: January 23rd 2009, 10:53 AM

Search Tags


/mathhelpforum @mathhelpforum