Calculating Time complexity for a transpose matrix

Question

The code is a summarized version of a piece of code trying to transpose a matrix. My task for this is to find the time complexity of this program.

I am only interested in the time complexity for the number of swaps that occur. I found out that on the outer loop for the swapping it occurs n-1 times and as for the inner loop it occurs (n^2 -n)/2 times.

---

I derived these solutions by subst n with a number.

• When n=4, my inner loop would loop 1+2+3 times
• When n=5, my inner loop would loop 1+2+3+4 times
• Therefore innerloop=(n^2 - n) / 2

How would i calculate the time complexity of this code?

---

I saw somewhere online where the person just took the values from his innerloop count and determine it was a O(n) complexity.

---

[Edit] Do i need to cater in the other loops to calculate the time complexity as well?

Answer 1

Your swap algorithm is a clear (1+2+3+...n) case, which translates to n×(n+1)/2.

Since constants and lower degree parts of a calculation don't count in Big O notation, this translates to O(n^2).

Taking in the other loops, won't change your time complexity, since they are also O(n^2). In terms of Big O, it doesn't make sense to write O(3(n^2)), because constants are dropped.

But what could help you here is that you don't need to bother with the more complex swap for loop. (I don't mean when you're learning. I mean, when you're dealing with real-world problems.)

On a side note, I would recommend reading example 3 of the Big O section in Cracking the Coding Interview (6th edition) (2015) by - McDowell, Gayle, which addresses this exact situation and many similar ones.