-2

i did some coding in java to find a missing number know my code is working. i have basic knowledge about how to check the complexity of the program and i have keen interest to learn about how can i do that please any one help me or suggest me to read some good tutorial. or help me to know somthing about asymptotic complexity related to my code. Thank You.

here is my code 

Scanner s1=new Scanner(System.in);
    System.out.println("Enter No:");
    int length=s1.nextInt();
    boolean isExit=false;
    int []a=new int[length-1];
    System.out.println("Enter all no");
    for(int i=0;i<length-1;i++){
    a[i]=s1.nextInt();
    }
    for (int i = 1; i<=length; i++) {
        for (int j = 0; j < a.length; j++) {
            if(i==a[j]){
             isExit =true;
             break;
            }
        }
        if (!isExit) {
            System.out.println(i);
            //break;
        }
        isExit = false;
    }
}

}

J.Kr
  • 3
  • 4

2 Answers2

0

I'm not sure if you're specifically trying to learn to do it all by hand? If not it's relatively easy to use streams to find the missing number:

Arrays.sort(array);
IntStream.range(0, array.length).filter(n -> !n.equals(array[n])).findAny();

That returns an Optional<Integer> which can then be tested to see if any missing number is present.

sprinter
  • 27,148
  • 6
  • 47
  • 78
-2

Read this : http://en.wikipedia.org/wiki/Big_O_notation

What you are looking to learn for is called asymptotic complexity.

A good video : Youtube

Also check out this answer What is a plain English explanation of "Big O" notation?

In relation to your post : 

for (int i = 1; i<=length; i++) {
        for (int j = 0; j < a.length; j++) {
            if(i==a[j]){
             isExit =true;
             break;
            }
        }
        if (!isExit) {
            System.out.println(i);
            //break;
        }
        isExit = false;
    }

Assuming that the operations inside your inner loop take constant time O(1).

If you think about this chunk of code in terms of code complexity you can notice that the outer loop will execute at most N(length) times and you can notice that the inner loop will execute N times too.Thus at most N^2 operations will be executed thus the upper bound of your algorithm is O(N^2) which means that the function N^2 will always be above the operations you make.

Community
  • 1
  • 1
Christo S. Christov
  • 2,268
  • 3
  • 32
  • 57