Help On Time Complexity Algorithm

[upside10]

I have this algorithm that is really giving e a problem can someone please help me.

void Transpose (int a[][SIZE], int n)
}
  for(int=1;i<n;i++)
      for(int j=i+1; j<=n; j++)
      {
         int t=a[i][j];
         a[i][j]=a[j][i];
         a[j][i]=t
       }
}

I need to obtain the time complexity of the above matrix transpose algorithm using program step count method.

Thanks for any help I can get on this.

[Inanna]

Work from the outside in. The outer loop goes from 1 to n - 1, so we can be lazy and call that O(n) 'cause it's close enough, right? So you know that whatever goes inside the outside loop steps n times, right? Now look at the inside loop. It varies from n to nothing, and because I'm assuming you want big-O notation, the biggest factor is applied. So the inside loop is O(n), right? Well, when you nest O(n) inside O(n), you get O(n^2).

Super math people might not appreciate that method because it's not exact. They can hold their breaths, leave the toilet seat up, or divide by zero, but it works...right? :)

[Rashakil Fol]

I don't see why a math person would have any problem with that reasoning.

[Inanna]

Me neither, but I was dying to make a crack about dividing by zero. :cheesy:

[upside10]

Thanks for the help. I figured out the inner loops.
int t= a[j]; (n-1)+(n-2)+(n-3)+...+1=(n-1)n
2
a[j]=a[j]; (n-1)+(n-2)+(n-3)+...+1=n(n-1)
2
a[j]= (n-1)+(n-2)+(n-3)+...+1= (n-1)
2
now I need help on finding T(n). I have to add (n-1)n + n(n-1) + (n-1)
2 2 2
together to find the answer. I have tried all formulas and still got the wrong answer. I got n-3
2
Thanks
upside10

[Infarction]

That doesn't look right. Each of statements in the innermost loop take constant (or close enough) time. What will change the execution time of this code is the loop conditions, both of which depend linearly on n. As they're nested, you have a situation of:

Outer loop, executes in O(n)
{
  Inner loops, which executes in O(n)
  {
    Constant time statements O(1)
  }
}

If you put these together, step by step you get the following:
- A: statements that execute in constant time.
- B: a loop which executes A in O(n) time.
- C: a loop which executes B in O(n) time, which is already executing A in O(n) time.

So you have O(n) iterations on the outer loop, each of which runs O(n) iterations on the inner loop, each of which runs in constant time. Overall, that's O(n) * O(n), which is O(n^2).

Long winded, but hopefully got the point across. ;) And as a little tip, this sort of analysis is based mostly on loop conditions; you'll pretty much ignore the other stuff ('cept function calls which in turn contain loops).

[upside10]

I figured it out. All inner steps should have the same answer. n(n-1) which in turn will give me 3n(n-1)/2 and from there I fugure time complexity.
Thanks
All for the help

That doesn't look right. Each of statements in the innermost loop take constant (or close enough) time. What will change the execution time of this code is the loop conditions, both of which depend linearly on n. As they're nested, you have a situation of:

Outer loop, executes in O(n)
{
  Inner loops, which executes in O(n)
  {
    Constant time statements O(1)
  }
}

If you put these together, step by step you get the following:
- A: statements that execute in constant time.
- B: a loop which executes A in O(n) time.
- C: a loop which executes B in O(n) time, which is already executing A in O(n) time.

So you have O(n) iterations on the outer loop, each of which runs O(n) iterations on the inner loop, each of which runs in constant time. Overall, that's O(n) * O(n), which is O(n^2).

Long winded, but hopefully got the point across. ;) And as a little tip, this sort of analysis is based mostly on loop conditions; you'll pretty much ignore the other stuff ('cept function calls which in turn contain loops).