1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Big O and little o notation

  1. Feb 2, 2008 #1
    1. The problem statement, all variables and given/known data

    1) Suppose T1(N) = O(f(N)) and T2(N) = O(f(N)). Which of the following are true?

    a) T1(N) + T2(N) = O(f(N))
    b) T1(N) - T2(N) = o(f(N))
    c) [tex] \frac{T_1(N)}{T_2(N)} = O(1) [/tex]
    d) T1(N) = O(T2(N))

    2) Find two functions f(N) and g(N) such that neither f(N) = O(g(N)) nor g(N) = O(f(N)).

    Just for clarity, I'm having to use these functions to analyze the running times of programs, with big O being the worst case running time.

    2. Relevant equations


    3. The attempt at a solution

    For problem 1, I know that letter "a" is true, but I'm having trouble with the rest. For letter "b", I know that T1(N) - T2(N) implies f(N) - f(N), which would be zero. So I believe letter "b" is false, because it's possible that T1(N) > T2(N). For part "c", if T2(N) is much smaller than T1(N), then the division would result in something much larger than 1, so I believe it to be fasle. Plus, I read that constants don't count in big O notation, so wouldn't O(1) just be O(0)? For part "d", T1(N) could be larger than T2(N) by the initial big O definitions, and thus I believe this to be false.

    For problem 2, I don't even know where to begin, because the problem implies that I must find two functions such that one is not greater than the other, and they cannot equal eachother either, right?

    Any help is appreciated.

    Edit: I changed my thoughts on part "b".
    Last edited: Feb 2, 2008
  2. jcsd
  3. Feb 3, 2008 #2

    Gib Z

    User Avatar
    Homework Helper

    Well, O(p) just means "within an error of a constant multiple of p".

    So it may help to write [tex]T_1 (N) = C_1 \cdot f(n), T_2 (N) = C_2 \cdot f(n)[/tex].

    That way, for a) the replacements make it become [tex](C_1 +C_2)\cdot f(n)[/tex]. And Since the new coefficient is just another constant, a) is also O(f(n)).
  4. Feb 3, 2008 #3
    Thanks for the reply. I've already figured out that letter "a" is true, but it's the rest that I'm having trouble with. I'm still stuck...
  5. Feb 3, 2008 #4

    Gib Z

    User Avatar
    Homework Helper

    Ok Lets think about this. For B) What if T_1 and T_2 are equal? They need not necessarily be, but lets take the case they are. Is it still O(f(n))?

    For c) From your attempt - as long as T_2 is only smaller than T_1 by a constant, then you get perhaps a big number but still a constant! And O(1) just means a constant! If T_2 is smaller than T_1 by so much that the number is infinitely large, then this contradicts that both are O( f(n) ).
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Big O and little o notation
  1. Big O notation (Replies: 1)

  2. Big-O Notation (Replies: 1)

  3. Little o notation (Replies: 5)