1.4 Problems

1.

Assuming that n is a power of 2, express the output of the following program in terms of n.

         int mystery (int n)
         { int x=2, count=0;
           while (x < n) { x *=2; count++}
           return count;
         }

2.

Show that the following statements are true:

(a)

${\frac{n(n-1)}{2}}$ is O(n²)

(b)

max(n³, 10n²) is O(n³)

(c)

$\sum_{i=1}^{n}$i^k is O(n^{k + 1}) and $\Omega$(n^{k + 1}), for integer k

(d)

If p(x) is any k^th degree polynomial with a positive leading coefficient, then p(n) is O(n^k) and $\Omega$(n^k).

3.

Which function grows faster?

(a)

n^{log n}; (logn)ⁿ

(b)

logn^k; (logn)^k

(c)

n^{logloglog n}; (log n)!

(d)

nⁿ; n!.

4.

If f₁(n) is O(g₁(n)) and f₂(n) is O(g₂(n)) where f₁and f₂ are positive functions of n, show that the function f₁(n) + f₂(n) is O(max(g₁(n), g₂(n))).

5.

If f₁(n) is O(g₁(n)) and f₂(n) is O(g₂(n)) where f₁and f₂ are positive functions of n, state whether each statement below is true or false. If the statement is true(false), give a proof(counter-example).

(a)

The function | f₁(n) - f₂(n)| is O(min(g₁(n), g₂(n))).

(b)

The function | f₁(n) - f₂(n)| is O(max(g₁(n), g₂(n))).

6.

Prove or disprove: If f (n) is a positive function of n, then f (n) is O(f (${\frac{n}{2}}$)).

7.

The running times of an algorithm A and a competing algorithm A^' are described by the recurrences 

T(n) = 3T($${\frac{n}{2}}$$) + n;        T^'(n) = aT^'($${\frac{n}{4}}$$) + n

respectively. Assuming T(1) = T^'(1) = 1, and n = 4^k for some positive integer k, determine the values of a for which A^' is asymptotically faster than A.

8.

Solve the following recurrences, where T(1) = 1 and T(n) for n $\geq$ 2 satisfies:

(a)

T(n) = 3T(${\frac{n}{2}}$) + n

(b)

T(n) = 3T(${\frac{n}{2}}$) + n²

(c)

T(n) = 3T(${\frac{n}{2}}$) + n³

(d)

T(n) = 4T(${\frac{n}{3}}$) + n

(e)

T(n) = 4T(${\frac{n}{3}}$) + n²

(f)

T(n) = 4T(${\frac{n}{3}}$) + n³

(g)

T(n) = T(${\frac{n}{2}}$) + 1

(h)

T(n) = 2T(${\frac{n}{2}}$) + log n

(i)

T(n) = 2T(${\frac{n}{2}}$) + n²

(j)

T(n) = 2T(n - 1) + 1

(k)

T(n) = 2T(n - 1) + n

9.

Show that the function T(n) defined by T(1) = 1 and 

T(n) = T(n - 1) + $${\frac{1}{n}}$$

                for n$\geq$ 2 has the complexity O(log n).

10.

Prove or disprove: f(3**n) is O(f(2**n))

11.

Solve the following recurrence relation: 

T(n) $$\leq$$cn + $${\frac{2}{n-1}}$$$$\sum_{i=1}^{n-1}$$T(i)

            where c is a constant, n$\geq$ 2, and T(2) is known to be a constant c₁.