Problem 58E

Big-O, Big-Theta and big-Omega notation can be extended to functions in more than one variable. For example, the statement f (x, y) is O (g(x, y)) means that there exist constants C, k1 , and k2 such that whenever x > k1 and y > k2 .

(Requires calculus) Show that if b > 1 and c and d are positive, then (logbn)c is O(nd), but nd is not O((logbn)c).

Solution:

Step1

Given that

We have to show that if b > 1 and c and d are positive, then (logbn)c is O(nd), but nd is not O((logbn)c).

Step2

The statement f (x, y) is O (g(x, y)) means that there exist constants C, k1 , and k2 such that whenever x > k1 and y > k2 .

Let us assume that f and g is functions from the set of integers.

We can say that f(x) is O(g(x)) if there are constants C and k such that

Where >k.

The constants C and k are said to be witnesses to the relationship.

If b>1 means all n

So, for C=1 and k=1

It is clear that is

Step3

For nd is not O((logbn)c)

It is not possible because exponential function will always grow faster than the logarithmic function.