CODEWITHSUNDEEP
runtimebig-ospace-complexity
Nych
Nych

Reputation: 78

Run time and space complexity of this code

I'm having a bit of trouble determining the big o of this solution I came up with on a CTCI question The space complexity should be O(1) but is the run time O(N)? It seems to be more towards O(N^2) because of the while loop. But the while loop does not run N times for each element inside the for loop.

public static int[] missing_two(int [] n){

        for(int i=0;i<n.length;i++){
            while(n[i]!=i){
                int temp=n[i];
                n[i]=n[n[i]];
                n[temp]=temp;
            }
        }

    }

Would 6,0,1,2,3,4,5 be an example of worst case here? The while loop will run n times on the first index. and 0 afterwards. Therefore shouldn't this be O(2n) => O(n)?

Upvotes: 0

Views: 92

Answers (1)

VMMF
VMMF

Reputation: 954

My understanding is that big O notation is used for giving an upper bound limit or a worst case scenario. The question you have to make yourself is: Could input vector n have values such that at least in one case, for all values in input vector n, the while loop is fully executed? Then a correct Big O notation would be O(N^2), if not but close, then I guess O(N^2) would still be a better estimation than O(N), as O(N) for an upper bound would have already been exceeded.

Now that you have edited the question and given more info about it I agree with you. It is O(N)

Upvotes: 1

Related Questions