I'm right about the time complexity on these situations?-CodePudding

I'm a little doubtful about the correctness of my assumptions when analyzing the time complexity of code like this. In this piece of code array.length() is considered as a linear complexity function. This last detail is important, the original exercise considered it was just a constant stored value, but I'm wondering what should happen if not):

void printPairs(int[] array) {
   for (int i = 0; i < array.length(), i  ) {
       for (int j = 0; j < array.length(), j  ){
          print(array[i], array[j])
       }
   }
}

So, if array.length was a variable inside array, like in java, all this thing would be just O(N^2). But what if array.length() is a function? His implementation should be linear...then...at first I tought it should become a O(N^4) code, but thinking better about it now I think is just O(N^3). But also I think that may be I'm wrong with both assumptions and it keep being O(N^2).

Can someone correct me? Thanks!

CodePudding user response：

j < array.length() is called array.length()*array.length() times.

If array.length() is O(1), then O(N^2). (e.g. C )

If array.length() is O(N), then O(N^3). (e.g. C strlen() although code may optimize it back to O(1))

CodePudding user response：

Chances are that the compiler can do a simple optimisation:

void printPairs(int[] array) {
   int n = array.length();
   for (int i = 0; i < n, i  ) {
       for (int j = 0; j < n, j  ){
          print(array[i], array[j])
       }
   }
}

And that is O(N^2)