0

I have gone through Asymptotic Notations. But I didn't see any clear visual representation and sample examples for the Asymptotic Notations.Anybody help me to get the clear representation for the same.

I have attached the same program herewith. Kindly tell me what notation it is following and how to find out what order it is using(O(n), nlogn or O(n2) etc). I have checked the time taken for the program is by System.currentTimeMillis() method.

The sample program is

public class ArrayPrblem {

public static void main(String[] args){
    int arr[] = {10,2,11,4,3,7,6};
    int brr[] = {11,3,12,4,7,9,12};
    for(int i=0;i<arr.length;i++){
        for(int j=0;j<brr.length;j++){
            if(i<j && arr[i] > brr[j]){
                System.out.println(""+(arr[i]+","+brr[j]));
            }
        }
    }
    System.out.println(+System.currentTimeMillis());
}

}

Kindly suggest me how to write a good optimized program by using this Asymptotic Notations.

Thanks in Advance

umamahes
  • 43
  • 1
  • 1
  • 11
  • As it currently stands, this question is too broad for the stack overflow format. I would recommend reading some background material and see if you still have difficulty then. [This question](http://stackoverflow.com/q/487258/2095090) is a great starting point, I think. – Vincent van der Weele Dec 29 '14 at 09:31

1 Answers1

0

Assuming arr and brr are NOT hard coded, but arguments, the complexity of the program is O(n*m), where n is the size of arr, and m is the size of brr. If they are both approximately (asymptotically) at the same length, that means the complexity is O(n^2).

You can arrive to this result by noticing that i runs from 0 to arr.length, and for each iteration, you have j, which runs from 0 to brr.length. This gives you total of brr.length * arr.length = m*n iterations.

As a side note, if arr and brr are hard coded - the complexity is constant and is noted as O(1) - as it will always take less time than some pre-known constant.

amit
  • 175,853
  • 27
  • 231
  • 333
  • Thank you so much for your reply. If the complexity is O(n^2) means it is worst case scenario right. O(n) is also worst case. n logn is the beast case right? Tell me whether my assumption is correct or not. – umamahes Dec 29 '14 at 10:06
  • @umamahes The worst case and best case of this algorithm are both `O(n^2)`. – amit Dec 29 '14 at 10:08
  • @umamahes if you mean that O(n^2) is the worst possible complexity for an algorithm, then no, certainly not. The complexity can get arbitrarily bad. – chiastic-security Dec 29 '14 at 10:13
  • @amit can you please suggest how to find out best and worst case for an algorithm ? – umamahes Dec 29 '14 at 10:36
  • @chiastic-security I believe he is refering to the Best Case/Worse Case/Average Case of a *specific* algorithm. – amit Dec 29 '14 at 11:44
  • @umamahes This is out of topic of this thread, but the idea is to find the "worst possible input" for the algorithm, and inspect how it behaves. In this case, the behavior is asymptotically identical for all inputs, so it does not come into consideration here. – amit Dec 29 '14 at 11:45