1. Suppose we have three functions f(n), g(n), and h(n) such that f(n) = O(h(n)) and g(n) = O(h(n)).
Must it be the case that f(n) = O(g(n))? Explain why or give a counterexample showing why not.
I think it is equal ! what you think ?
2. Write a recurrence describing the number of times the following algorithm compares two members of array A, measured as a function of the array length n. Solve this recurrence.
fibsort(long A[], int n)
{
if (n <= 1) return;
if (A[0] > A[n-1]) swap A[0] and A[n-1];
fibsort(A+1, n-2);
if (A[0] > A[1]) swap A[0] and A[1];
fibsort(A+1, n-1);
}
I think it is : 2n + 1?
I hope to helpme on them >>>