Time complexity of nested for-loop with two independent variables

Question

I am trying to calculate the time complexity of this function:

int fun1(A, k){ //A is an array, k is an integer
n = length(A); //length of array
for j:= 1 to k{
 for i:= j to n{
 if A[i] < A[j-1]{
 x:= A[j-1]; 
 A[j-1]:= A[i]; 
 A[i]:= x
 }
 }
}
return A[k-1]}

We iterate k times in the outer loop, but how to calculate number of iterations of inner loop, and then the time complexity of entire algorithm?

Answer 1

Since the work inside the double loop is constant and assuming that k<=n then the complexity can be written as

enter image description here

Edit: I forgot the constant but it doesn't matter as it will disappear inside the big Oh notation

• SDstack: How did you recive from (sum C, i = j to n) to (n - j + 1)? It should not be (n - j + 1)(n + j)? Thank you for your answer.
• Hikmat Farhat: Since C is constant you factor it out then the inner sum becomes sum(i=j to n) of 1 which is (n-j+1). For example, sum(3 to 5) of 1 is 1+1+1=3=(5-3+1)