- #1

- 436

- 0

## Homework Statement

1) Suppose T

_{1}(N) = O(f(N)) and T

_{2}(N) = O(f(N)). Which of the following are true?

a) T

_{1}(N) + T

_{2}(N) = O(f(N))

b) T

_{1}(N) - T

_{2}(N) = o(f(N))

c) [tex] \frac{T_1(N)}{T_2(N)} = O(1) [/tex]

d) T

_{1}(N) = O(T

_{2}(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

_{1}(N) - T

_{2}(N) implies f(N) - f(N), which would be zero. So I believe letter "b" is false, because it's possible that T

_{1}(N) > T

_{2}(N). For part "c", if T

_{2}(N) is much smaller than T

_{1}(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

_{1}(N) could be larger than T

_{2}(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: