Are These Statements True for Big O and Little o Notation?

[hotcommodity]

Homework Statement

1) Suppose T₁(N) = O(f(N)) and T₂(N) = O(f(N)). Which of the following are true?

a) T₁(N) + T₂(N) = O(f(N))
b) T₁(N) - T₂(N) = o(f(N))
c) \frac{T_1(N)}{T_2(N)} = O(1)
d) T₁(N) = O(T₂(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.

Homework Equations

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 T₁(N) - T₂(N) implies f(N) - f(N), which would be zero. So I believe letter "b" is false, because it's possible that T₁(N) > T₂(N). For part "c", if T₂(N) is much smaller than T₁(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", T₁(N) could be larger than T₂(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 each other either, right?

Any help is appreciated.

Edit: I changed my thoughts on part "b".

 

[Gib Z]

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

 

[hotcommodity]

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]

Ok Let's think about this. For B) What if T_1 and T_2 are equal? They need not necessarily be, but let's 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) ).