Finding the complexity of given code

Question

I am battling to find the complexity of given code. I think I am struggling with identifying the correct complexity and how to actually analyze the complexity. The code to be analyzed is as follows:

    public void doThings(int[] arr, int start){
    boolean found = false;
    int i = start;
    while ((found != true) && (i<arr.length)){
        i++;
        if (arr[i]==17){
            found=true;
        }
    }
}
public void reorganize(int[] arr){
    for (int i=0; i<arr.length; i++){
        doThings(arr, i);
    }
}

The questions are:

1) What is the best case complexity of the reorganize method and for what inputs does it occur?
2) What is the worst case complexity of the reorganize method and for what inputs does it occur?

My answers are:

1) For the reorganize method there are two possible best cases that could occur. The first is when the array length is 1, meaning the loop in the reorganize and doThings method will run exactly once. The other possibility is when the ith item of the array is 17 meaning the doThings loop will not run completely on that ith iteration. Thus in both cases the best case=Ο(n).

2) The worst case would be when the number 17 is at the end of the array and when the number 17 is not in the array. This is will mean that the array will be traversed n×n times meaning the worst case would be Ο(n^2 ).

Could anyone please help me answer the questions correctly, if mine is incorrect and if possible explain the problem?

Reorganize is a terrible name. It just searches – OneCricketeer Nov 10 '16 at 15:09 — OneCricketeer, Nov 10 '16 at 15:09
I am not seeing `nxn`...for me is just `O(n)` in both cases – Hackerman Nov 10 '16 at 15:12 — Hackerman, Nov 10 '16 at 15:12

score 0 · Accepted Answer · edited May 23 '17 at 12:01

"best case" the array is empty, and you search nothing.

The worst case is that you look at every single element because you never see 17. All other cases are in between.

if (arr[i]==17){ is the "hottest path" of the code, meaning it is ran most often.

It will always execute a total of n*(n-1)/2 times (I think I did that math right) in the worst case because even when you set found = true, the reorganize method doesn't know about that, doesn't end, and continues to search even though you already scanned the entire array.

Basically, flatten the code without methods. You have this question.

What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?

Finding the complexity of given code

1 Answers1