Can I ask somebody to help me start with this algorithm's time complexity?

I'm specifically trying to figure out how can get the Big O.

Few things I think I know is that the while is probably O(n) and the 'for' is O(n) because of the T.length which gives it not to be a constant. But I'm not sure if this means that the whole algorithm probably will be O(n^2) or just simply O(n) or am I in the complete wrong path?

The function's description says that it supposed to do 'SquareRootByItems'.

int function(int T[]){
for (int i := 0; i < T.length; i  ){
    int j := 1;
    while(j * j <= T[i]) j  ;
    T[i] := j;
  }
  return 0;
}

Thanks everybody for their help.

CodePudding user response：

The outer loop (for (int i := 0; i < T.length; i )) here is going to be O(n) where n represents T.length, and the loop only executes once per element of the array.

For the inner loop (while(j * j <= T[i])), let k = T[I]. The worst case scenario is when every element has value O(k). Then j * j (j^2) will be O(k) when the loop is done, so for the inner loop the complexity will be O(sqrt(k)).

Lastly, we multiply these two to get the total complexity because it's a nested loop. So the end result is O(n * sqrt(k))

Credit to @GeneralGrievance for helping.