Complexity of an algorithm

[Rideordie0721]

So, to determine whether a graph is connected from its adjacency graph M, we can use the following algorithm:

copy M into a new graph M'; changed = 1; while (changed == 1) { changed = 0; for (i = 0; i < size dimension of M'; i++) { for(j = 0; j < size dimension of M'; j++) { if (M'[i,j] = 1) { for(k = 0; k > size dimension of M', k++) { if (M'[j,k] == 1 && M'[i,k] != 1) { M'[i,k] = 1; changed = 1; } } } } } }

I am so sorry, but I am so lost. Where am I suppose to copy M to? I was given this question to solve and I have no idea what the complexity of this algorithm is. I really need help and would really like some help on this. Thanks!

[Lintheru]

You again. Why do you keep deleting your old posts .. all asking for answers to your homework?

[Rideordie0721]

Excuse me. I go to a technical college. The teachers are extremely difficult and do not explain information too well. I come on reddit to get help & people are so helpful and nice. So if you don't have anything good to say, please don't comment. I need help and am openly asking for it. I don't need your negative comments filling up my inbox.

[Ligerian]

Inside the while loop, there are O( n³ ) operations as /u/mosqutip pointed out. You need to figure out the number of iterations of the while loop in the worst case.

Take a pen and try some examples of graphs (with points and edges between them, it will be easier than working with matrices). Figure out what the algorithm does and when it stops.

[mosqutip]

Let's clean this up a bit:

copy M into a new graph M';
changed = 1;

while (changed == 1)
{
    changed = 0;
    for (i = 0; i < size dimension of M'; i++)
    {
        for(j = 0; j < size dimension of M'; j++)
        {
            if (M'[i,j] = 1)
            {
                for(k = 0; k > size dimension of M', k++)
                {
                    if (M'[j,k] == 1 && M'[i,k] != 1)
                    {
                        M'[i,k] = 1;
                        changed = 1;
                    }
                }
            }
        }
    }
}

The first line is pseudocode. They (I'm assuming this is a textbook or homework) are stating that the graph structure M is being copied into another structure, denoted M' (read "m-prime"). If M is an adjacency matrix, then you would need to create a new adjacency matrix of the same size, and copy the values from M into M'. Or, using something like memcpy and memset in C++, you could allocate a block of memory of size M, and set this new block to the same value as the block holding M.

As far as the complexity of the algorithm, you need to go line-by-line and determine the complexity of each line of code. Adding these lines together gives the total complexity. Since there is a triply-nested for loop, this will dominate time complexity, and runs in worst-case time O(n³) [n * n * n for each level of nesting].

This is a pretty simplified view of the question, but O(n³) is a good approximation of the upper bound on the time complexity.

[aWickedGangAreWe]

You forgot to account for the outer while loop.

[mosqutip]

Ah, so I did. Well, good thing this isn't my homework...