# Big O and little o notation

## Homework Statement

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) $$\frac{T_1(N)}{T_2(N)} = O(1)$$
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.

None.

## 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:

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

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

That way, for a) the replacements make it become $$(C_1 +C_2)\cdot f(n)$$. And Since the new coefficient is just another constant, a) is also O(f(n)).

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

Gib Z
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) ).