Big O Complexity for Matlab code - euclidean distance between each element in matrix A(n*n)

i want to compute Big O complexity for this Matlab code , the challenge i have is how to compute complexity for "sum, size and traspose "of matrix operations

the code is

A=[0 1 1 0 ; 1 0 1 1 ; 1 1 0 1 ; 0 1 1 0];

k=full(sum(A))

num_edges=sum(k)

kkk=full(sum(A,2)');

n = size(A,1)  % number of nodes

ff=zeros(n,n);

gg=zeros(n,n);

for i=1:n

      for j=1:n

         for q=1:n
          q;
          i,j;
             if(kkk(q)==0)
               gg(i,j)=A(i,j);
             else
                gg(i,j)=gg(i,j)+(((A(q,i)-A(q,j)).^2)/(n));
             end

         end
         gg(i,j)=gg(i,j).^0.5;
      end

end

gg=gg

Thank you,

Answer 1

[Walter Roberson]

The complexity of the size() operation is O(1)

The cost of sum() is number of items being totaled at a time, multiplied by number of times that has to happen. That is going to come out the same as the number of elements in the matrix. Which makes sense: every element only needs to be examined once.

The cost of a transpose is the same as the number of items being transpose.

Your code does not need to do the transpose.

Your code is not calculating Euclidean distance. Euclidean distance does not divide by n. I also think your check of kkk(q) is wrong -- at least it would be if you could potentially have negative entries.

Calculating Euclidean distance between each two items in the matrix would require n^4 output locations (or half of that for a triangular version that takes advantage of symmetry.)

[mai saad]

Thank you, euclidean distance doesn't divide by n but i want to make a normalization

[mai saad]

"This is my first time really computing Big O, i want to check if my result true. and i have a challenge with if statements, help me please"

A=[0 1 1 0 ; 1 0 1 1 ; 1 1 0 1 ; 0 1 1 0]; % n:rows & n:columns

k=full(sum(A))   >>>>>>>>>>>>>>>>>>> O(n^2)

num_edges=sum(k)  >>>>>>>>>>>>>>>>>>>>O(n^3)

kkk=full(sum(A,2)');  >>>>>>>>>>>>>>>>O(n^4)

n = size(A,1)  % number of nodes   >>>>>>>>>>>>>O(1)

ff=zeros(n,n);   >>>>>>>>>>>>>>>>>>O(n^2)

gg=zeros(n,n);   >>>>>>>>>>>>>>>>>O(n^2)
>>>>>>>>>>>>>>>>>>>>>>>>>>>loop=O(n*n*n)=O(n^3)
for i=1:n

        for j=1:n

           for q=1:n

            q;

            i,j;

               if(kkk(q)==0)

                 gg(i,j)=A(i,j);

               else

                  gg(i,j)=gg(i,j)+(((A(q,i)-A(q,j)).^2)/(n));

               end

           end

           gg(i,j)=gg(i,j).^0.5;

        end

end

gg=gg

thanks for you

[Jan]

Please format your code properly. Remove the blank lines and use the "{} Code" button.

Remove the useless lines "q;" and "i,j;" . And finaly tell us the problem you need help for.

[mai saad]

ok, thank you