For all pairs of functions below, show whether f(n) is O(g(n)) or g(n) is O(f(n)) (or both). f(n) g(n) (a) n3 n4 . n3 (b) log2 2n ln 2n (c) 5 log n...

3. For all pairs of functions below, show whether f(n) is O(g(n)) or g(n) is

O(f(n)) (or both).

f(n) g(n)

(a) n3 n4 .. n3

(b) log2 2n ln 2n

(c) 5 log n log(n3)

(d) (log n)2 (log n)3

(e) n! 2n

4. Consider the following algorithm:

1: function SumElement(array A)

2: if length(A) == 1:

3: return A[0]

4: else:

5: A1 A[0 : length(A)=3]

6: A2 A[length(A)=3 : 2 length(A)=3]

7: return SumElement(A1) + SumElement(A2)

8: end function