# Big O and little o notation

1. Feb 2, 2008

### hotcommodity

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

2. Relevant equations

None.

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. Feb 3, 2008

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

3. Feb 3, 2008

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

4. Feb 3, 2008

### Gib Z

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