Big O and little o notation

  • #1
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 eachother either, right?

Any help is appreciated.

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

Answers and Replies

  • #2
Gib Z
Homework Helper
3,346
6
Well, O(p) just means "within an error of a constant multiple of p".

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

That way, for a) the replacements make it become [tex](C_1 +C_2)\cdot f(n)[/tex]. And Since the new coefficient is just another constant, a) is also O(f(n)).
 
  • #3
436
0
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
Gib Z
Homework Helper
3,346
6
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) ).
 

Related Threads on Big O and little o notation

  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
3
Views
11K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
18
Views
35K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
1K
Top