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?

Hikmat Farhat · Accepted Answer · 2020-11-01 18:56:32Z

1

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

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

answered Nov 1, 2020 at 18:56

Hikmat Farhat

5923 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

SDstack Over a year ago

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 Over a year ago

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)

Collectives™ on Stack Overflow

Time complexity of nested for-loop with two independent variables

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related