- #1
hotcommodity
- 436
- 0
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) [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.
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 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 each other either, right?
Any help is appreciated.
Edit: I changed my thoughts on part "b".
Last edited: