Question

Question 2 Consider the following algorithm Fun that takes array A and key Kas Fun(AO,...,n - 1], K) count = 0 for i = 0 ton - 1 do for j = i +1 to n - 1 do if A[i] + A[j] == K then count = count +1 end if end for end for return count What is the best case time complexity of the above algorithm?! (log(n)) O(1) (n) (na) Previous o H H 9

Answer 1

Θ(n2)

The variable i goes from 0 to n-1. The variable j goes from i+1 to n-1. So for i=0, j goes from 1 to n-1 or n-1 iterations, for i=1, j goes from 2 to n-1 or n-2 iterations, up to i=n-1 when j goes from n to n-1, which is 0 iterations since starting point is greater than ending point. So, the total number of iterations is (n-1)+(n-2)+....+1+0 = (n-1)(n-1+1)/2 = n(n-1)/2 = (n2-n)/2. In the best case of the function, the if-condition will always be false and none of the operations will be executed. So, only the comparison in the condition of the if will be executed inside the loop. So, it will have a total of (n2-n)/2 operations in the best case. So, the best case time complexity is Θ(n2) since the highest power of n is always selected.