CODEWITHSUNDEEP
javatime-complexity
Harshit Jain
Harshit Jain

Reputation: 79

what is the time complexity of given code

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

Upvotes: 1

Views: 922

Answers (4)

SSH
SSH

Reputation: 1627

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.

Upvotes: 1

shipperizer
shipperizer

Reputation: 1669

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

Upvotes: 0

rakesh99
rakesh99

Reputation: 1266

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

Upvotes: 0

Abhijeet Dhumal
Abhijeet Dhumal

Reputation: 1809

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.

Upvotes: 5

Related Questions