Would this n x n transpose algorithm be considered an in place algorithm?-CodePudding

Based on my research, I am gaining conflicting information about this simple algorithm. This algorithm is a basic matrix transposition, that transposes an n x n matrix A.

My current understanding is this algorithm would run at O(n^2) time and have a space complexity of O(1) as the matrix we manipulate would be the same one we deal with.

But- I have also been told it would actually run O(n) time and have space complexity of O(n) as well. Which means it wouldn't be in-place, as it requires extra space for manipulation.

Which thought process is correct here for the transpose algo below?

Transpose(A) 
  1. for i = 1 to n -1 
  2.    for j = i   1 to n 
  3.      exchange A[i, j] with A[j,i]

CodePudding user response：

Some confusion might arise from the facts that the workload is proportional to the number of elements in the array, and these elements occupy their own space. So by some notation abuse or inattention, both would be said "O(n)".

But this is wrong because

n is clearly not the number of elements but the number of rows/columns of the array;
by definition the space complexity does not include the input and output data, but any auxiliary space that would be required.

Hence we can confirm the time complexity O(n²) - in fact Θ(n²) - and space complexity O(1). The algorithm is in-place.

Final remark:

If we denote the number of elements as m, the time complexity is O(m), and there is no contradiction.