Given two randomly ordered integer arrays A and B each of n integer numbers. Consider the following function:

Question

bool Quiz (int A[0..n-1 ], int B[0..n-1 ], int n) {

int k = 0;

for (i = 0; i < n; i++) if (A[i] == B[i]) k++;

if (k == n) return false;

Sort (A , n);

Sort (B , n);

for (i = 0; i < n; i++)

if (A[i] != B[i])

return false;

return true;

}

Find T(n) = number of comparisons needed for Quiz to return the result and its worst case complexity in terms of n? if the function Sort(X,n) does n log(n) comparisons to sort an arrays of x

should i add the the n+nlog(n) + nlog(N) + n or i multiply them to get T(n)?

Answer 1

You should add them. The worst case will be the $n \log{n}$.

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

Your upper bounding function will be $n \log{n}$.

$$ O(n \log{n}) $$