# algorithm analysis help

• 06-01-2011
nik
algorithm analysis help
the site doesnt let me post my question although I use code tags

hi guys i have this exercise and I m not sure if I'm correct [CODE]for (i=0 - Pastebin.com

thanks

hi guys

<<< Copy/Pasted by mod >>>
i have this exercise and I m not sure if I'm correct
Code:

```for (i=0;i<=n-2;i++){     for(j = i+1; j<= n-1; j++){           if (A[i,j] != A[j,i])                 return false;           }   }```
a. What does this algorithm compute?
b. What is its basic operation?
c. How many times is the basic operation executed?
d. What is the efficiency class of this algorithm?
e. Suggest an improvement or a better algorithm altogether and indicate its efficiency class. If you cannot do it, try to prove that in fact it cannot be done.

a. it checks to see if the array is symmetrical
b. the if operation
c. http://latex.codecogs.com/gif.latex?...{j=i+1}^{n-1}1
d. O(n^2), can this be Θ(n^2)?
e. i dont think we can, since we have to check all the arrays elements to see if they match