What is the complexity of this program?

Question

I want to analyze the execution time complexity of the below program. Please answer with the explanation.

private static void printSecondLargest(int[] arr) {
    int length = arr.length, temp;
    for (int i = 0; i < 2; i++) {
        for (int j = i+1; j < length; j++) {
            if(arr[i]<arr[j]) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println("Second largest is: "+arr[1]);
}

The inner loop runs `(2* arr.length)-2` times *totally*. The complexity is `O(n)` — TheLostMind, Feb 18 '15 at 11:16
@TheLostMind thanks for answering. However your answer is correct but the explanation is slightly incorrect. it'll execute (2* arr.length) - 3 times. — Rahul Chaubey, Feb 18 '15 at 11:37

aioobe · Accepted Answer · 2015-02-18T11:23:06.547

3

It's O(n) where n represents the length of the array.

The body of the inner most loop:

if(arr[i]<arr[j]) {
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

runs in constant time.

This code will be executed first arr.length-1 times, then arr.length-2 times. That is 2 * arr.length - 3. Thus the execution time is proportional to 2n-3 which is O(n).

edited Feb 18 '15 at 11:23

answered Feb 18 '15 at 11:16

aioobe

413,195
112
811
826

How did you get 4n? Two executions = 2n? – aioobe Feb 18 '15 at 11:33
Thanks aioobe. Do u know any better approach to solve it in C? – Rahul Chaubey Feb 18 '15 at 11:39
You can't do better than O(n), but see for instance [this question](http://stackoverflow.com/questions/25490946/how-to-find-the-second-largest-element-using-c-program-without-using-array) for alternative implementatios. Also, please read [this](http://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work). – aioobe Feb 18 '15 at 11:41
1

@bigdestroyer, code won't execute (2*n -3) twice. it will n-1 first time and n-2 second time, so n-1 + n-2 = 2n-3 in total. – Rahul Chaubey Feb 18 '15 at 11:44

score 1 · Answer 2 · answered Feb 18 '15 at 14:28

1

It is clearly O(n). The outer loop is running only 2 times and inner loop N times. So, overall complexity is O(2*n).

answered Feb 18 '15 at 14:28

Ankita Singh

107
1
5

score 0 · Answer 3 · answered Feb 18 '15 at 11:19

0

The outer loop will run two times and inner loop runs (length-1) and second time (length-2)

suppose length is N

so it will be 2*((N-1)/2+(N-2/)2)==2*(2n-3)/2

Which is final (2N-3) and in O notation it is O(N)

answered Feb 18 '15 at 11:19

squiroid

13,809
6
47
67

1

`(N-2/)2`? And where does `/2` come from to begin with? – aioobe Feb 18 '15 at 11:21
common LCM of N-1/2 and N-2/2:-) – squiroid Feb 18 '15 at 11:22
Yup average of two inner iteration – squiroid Feb 18 '15 at 11:24
But averaging is completely redundant. You must *sum* all the runtimes, not *average* them. – Marko Topolnik Feb 18 '15 at 11:25
Actually i used 2* in the initial step which is representing the number of iterations of the loop so i have to take the average of time consumed by all :-) And sorry yup it is redundant :-) – squiroid Feb 18 '15 at 11:27
Should i delete the answer ? – squiroid Feb 18 '15 at 11:27

score 0 · Answer 4 · edited Feb 18 '15 at 13:17

private static void printSecondLargest(int[] arr) {    
    int length = arr.length, temp;    // **it takes contant time**
    for (int i = 0; i < 2; i++) {     // as loop goes only two step it also takes constant time
        for (int j = i+1; j < length; j++) {   // this loop takes n time if we consider arr length of size n
            if(arr[i]<arr[j]) {
                temp = arr[i];    // it also takes constant time
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println("Second largest is: "+arr[1]);
}

So as per above calculation we neglect constant time and calculate all varying time constraint and as per code complexity will be O(n).

What is the complexity of this program?

4 Answers4