Java Best and Worst case complexity

Question

What is best and worst case in this java program. I think worst case is O(n^2) and Best case O(n) or maybe O(1). Can I simply say best case in O(1) in case the list is already sorted? What if an array is empty? will it make the best case O(0)? Can anybody please explain it to me.

Thank you in Advance

     public class playground {
      static void printSimpleMedian(int[] arr) {
    if (arr == null || arr.length == 0) {
        System.out.println("Array is empty");
    } else {
        boolean sorted = true;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                sorted = false;
            }
        }
        if (!sorted) {
            for (int i = 0; i < arr.length / 2; i++) {
                int max = i;
                int min = i;
                for (int j = i; j < arr.length - i; j++) {
                    if (arr[max] < arr[j]) {
                        max = j;

                    }
        //System.out.print(max);
                }

                for (int j = i; j < arr.length - i; j++) {

                    if (arr[min] > arr[j]) {
                        min = j;
                    }
                    //System.out.print(min);
                }

                int tmp = arr[i];

                arr[i] = arr[min];

                arr[min] = tmp;

                tmp = arr[arr.length - i - 1];

                arr[arr.length - i - 1] = arr[max];

                arr[max] = tmp;
            }
        }

        // if array length is even upper median is chosen

        System.out.println(arr[arr.length / 2]);
        }
    }



  }

"What if an array is empty" You don't ask yourself that question when assessing the asymptotic complexity. You want to make a judgement about the behaviour of the algorithm when the size of the input tends towards infinity — Niklas B., May 11 '14 at 15:36

score 0 · Answer 1 · edited May 23 '17 at 12:13

After a quick glance here are my two cents:

I don't think that O(0) makes any practical sense. I'd have a look at this link: Is the time complexity of the empty algorithm O(0)?. I'd say that for an empty array it runs in constant time, O(1), but I am not sure that the special case of having no input should count as best case... along the lines of this logic, I think we could state that all algorithms' complexity is constant for the best case, and to me that seems to defeat the purpose of the whole O-notation-thing.
In the best case, when the array is sorted, you are doing comparison operations O(n) number of times.
In the worst case you are running the first loop once, that is O(n), the second loop once, that has two separate inner loops, so that's O(n*2n) = O(2n^2) = O(n^2), so that is O(n + n^2) = O(n^2).

Thank you. I was really confused between O(n) and O(1). – MessitÖzil May 11 '14 at 15:06 — MessitÖzil, May 11 '14 at 15:06

Java Best and Worst case complexity

1 Answers1