Hello, I would like to get help with the following questions, thanks in advance.

3. Suppose T(n) = O(f(n)) and R(n) = O(g(n)) for positive valued functions T(n), R(n), f(n), g(n), for n>=1.

1. Prove that: T(n) + R(n) = O( f(n) + g(n) )

2. Prove that T(n)*R(n) = O( f(n)*g(n) )

3. Disprove the claim that T(n)/R(n) = O( f(n)/g(n) ), i.e., provide a counter example.

4. Understanding and Applying Lower Bounds

Suppose Dr. WhyLie comes up to you and claims that he has invented a super-fast comparison based priority queue. The speed of the priority queue operations are as follows (n is the number of items currently in the priority queue):

a. insert a new item in O(sqrt(log n)) time

b. extract (remove and return) the smallest item from the priority queue in O(sqrt(log n)) time.

Explain why Dr. WhyLie must be lying.