Question

float useless(A){ n = A.length; if (n==1) { return A[@]; let A1,A2 be arrays of size n/2 for (i=0; i <= (n/2)-1; i++){ A1[i] = A[i]; A2[i] = A[n/2 + i]; for (i=0; i<=(n/2)-1; i++){ for (j=i+1; j<= (n/2)-1; j++){ if (A1[i] == A2[j]) A2[j] = 0; b1 = useless(A1); b2 = useless (A2); return max(b1,b2); What is the asymptotic upper bound of the code above?

Answer 1

complexity of first for loop is n/2 = O(n) times.
complexity of second for loop is O(n^2) times.
so, work done inside a recursive call is O(n^2)
two recursive calls are made of size n/2
so, recurrence relation is T(n) = 2T(n/2) + O(n^2)

$T(n) = 2T(n/2) &plus; O(n^2)\\ This\; is \;in \;the \;form\;of \;T(n) = aT(\frac{n}{b}) &plus; f(n)\\ so,\;we\;can\;use\;master's\;theorem.\\ compare\;n^{\log_b{a}}\;with\;f(n)\\ a=2,\;b=2\;\\ n^{\log_b{a}}=n^{\log_2{2}}=n^{1}=n\\ n^{\log_b{a}}=n^{\log_2{2}}=n^{1}=n\;<\;f(n)=O(n^2)\\ so,\;this\;comes\;under\;case\;3\\ so,\;time\;complexity\;is\;O(f(n))=O(n^2)\\$Answer: O(n2)