what is the time complexity of given code

Question

import java.util.Scanner;


public class PairsOfElementsSumEqualsN {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner s  = new Scanner(System.in);

        System.out.println("enter the number");

        int n = s.nextInt();

        int[] array = new int[]{1,2,1,2,4,5,6,7,8,9};

        int j = 0;
        int i = 0;

        for(i = 0 ; i<array.length;i++)
        {
            for(j=i+1;j<array.length;j++)
            {
                if(array[i] + array[j] == n)
                {
                    System.out.println(array[i] + "," + array[j]);
                }

            }
        }

    }

}

i think it should be n^2 but i want an explanation for the answer

Abhijeet Dhumal · Accepted Answer · 2015-06-25 19:11:32Z

5

Yes you are correct its time complexity is O(n^2).

You are doing n-1 comparisons in 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So the total number of comparisons will be.

(n-1)+(n-2)+(n-3)+.....+3+2+1
Sum = n(n-1)/2
i.e O(n^2)

This is because big-O notation describes the nature of the algorithm. The major term in the expansion (n-1) * (n-2) / 2 is n^2. And so as n increases all other terms become insignificant.

answered Jun 25, 2015 at 19:11

Abhijeet Dhumal

1,80914 silver badges24 bronze badges

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

Comments

SSH · Accepted Answer · 2015-06-25 20:30:31Z

1

yes it is n^2 because your both loops iterate over the entire limit and hence you have n times first loop into (n-1) times second loop leads to n^2.

edited Jun 25, 2015 at 20:30

answered Jun 25, 2015 at 19:09

SSH

1,6372 gold badges24 silver badges43 bronze badges

1 Comment

RealSkeptic Over a year ago

They iterate over the entire array in any case, there is no breaking condition. Also note that the second loop is only starting at i+1 so it's not running a full N. It's still n squared, but it needs explaining why.

rakesh99 · Accepted Answer · 2015-06-25 19:15:54Z

0

Just count the operations

Outer loop 1st
   Inner Loop N-1 times
     print and if body are constant i.e O(1)

Outer loop 2nd
   Inner Loop N-2 times
     print and if body are constant i.e O(1)

...
Outer loop N-1th time
   Inner Loop 1 times
     print and if body are constant i.e O(1)

Outer loop N-1 time
   Inner Loop 0 times
     print and if body are constant i.e O(1)

Total (N-1)+(N-2)+...+1 =N^2-N(N+1)/2

answered Jun 25, 2015 at 19:15

rakesh99

1,26620 silver badges35 bronze badges

Comments

shipperizer · Accepted Answer · 2015-06-25 19:16:24Z

0

basically as @SSH said it's the worst case scenario, even if you have a constant case where, eg, you do that if block for even Js, the result of the algorithm would be nn/2 but for n going to infinite that "divide by 2" is irrelevant. For the same reason every addition to the complexity (nn/2 + 5 or n*n -5) is irrelevant as n is gonna be "pushing" to infinite

answered Jun 25, 2015 at 19:16

shipperizer

1,6791 gold badge13 silver badges20 bronze badges

Collectives™ on Stack Overflow

what is the time complexity of given code

4 Answers 4

Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related