Show that 2n is O(3n) but that 3n is not O(2n). (Note that this is a special case of Exercise 60.)

Solution:Step 1In this problem we have to show that but that Function is called if there exist constant c and k such that where Step 2By method of contradiction we will show that, Let us assume that for a pair of witnesses for c and k exist such that we have whenever n > k. Now, when n >0 we can take log on both side of the inequality Or, Since, we know...