specifically what is 2c? why is it [n(n-1)]/2? Consider the following algorithm.
ID: 3882294 • Letter: S
Question
specifically what is 2c? why is it [n(n-1)]/2?
Consider the following algorithm. ALGORITHM Enigma(A[0..n-1,0..n-1])) for j = 0 to n-2 do for k = j+1 to n-1 do if A[j, k] notequalto A[k, j] return false return true a. What does this algorithm compute? b. What is its basic operation? c. How many times is the basic operation executed? d. What is worst-case time complexity of this algorithm? e. Suggest an improvement or a better algorithm altogether and indicate its worst case time complexity. If you cannot do it, try to prove that in fact it cannot be done.Explanation / Answer
The input is a 2-D matrix of n rows and n columns.
The first for loop works from j=0 to j=n-2, a total of (n-2)-(0) + 1 = (n-1) times.. That means inner loop was executed (n-1) times.
The inner loop works for k=j+1 to k=n-1,
So for j=0, k=1 to k=n-1, a total of (n-1)-(1)+1 = (n-1) times
So for j=1, k=2 to k=n-1, a total of (n-1)-(2)+1 = (n-2) times
.. and so on
for j=n-2, k=n-1 to k=n-1, a total of (n-1)-(n-1)+1 = (1) times
Hence if we calculate how many times the comparison A[j,k] and A[k,j] happens is, as below:
(n-1) + (n-2) + .... + 1 [total of n-1 terms]
As we know the sum of the series from 1 to n is n(n+1)/2,
Hence applying the same formula for the sum of (n-1) terms,
The answer will be (n-1)(n-1+1)/2, i.e. [n(n-1)]/2
Hence Proved.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.