1

I wrote a function to find the position where the target value should be inserted in the given array. We assume the array has distinct values and is sorted in ascending order. My solution must be in O(log N) time complexity

public static int FindPosition(int[] A, int target) {


    int a = A.length / 2;
    System.out.println(a);
    int count = a;
    for (int i = a; i < A.length && A[i] < target; i++) {
        count++;
    }
    for (int i = a; i > A.length && A[i] > target; i--) {
        count++;
    }
    return count;
}

Does this code have complexity of O(log N)?

raju
  • 209
  • 7
  • 19

2 Answers2

1

Short answer

No.

Longer answer

With increments of 1 in your indices, you cannot expect to have a better solution than O(n).

If your algorithm works at all (I don't think it does), it looks like it would need O(n) steps.

Also, you say you assume that the array is sorted, but you sort it anyway. So your code is O(n*log(n)).

What's more, trying to sort an already sorted array is the worst case for some sorting algorithms : it might even be O(n**2).

You're looking for a binary search.

Community
  • 1
  • 1
Eric Duminil
  • 52,989
  • 9
  • 71
  • 124
1

No it isn't nlogn

public static int FindPosition(int[] A, int target){
/*
Time taken to sort these elements would depend on how
sort function is implemented in java.  Arrays.sort has average 
time complexity of Ω(n log n), and worst case of O(n^2)
*/
Arrays.sort(A);


/*Time taken to run this loop = O(length of A) or O(N) 
where N = arraylength
*/

for(int i=a;i<A.length&&A[i]<target;i++){
    count++;
}
/*Time taken to run this loop = O(length of A) or O(N) 
where N = arraylength
*/
for(int i=a;i>A.length&&A[i]>target;i--){
    count++;
}
return count;
}

Now time complexity would be represented by the longest of above three, since assignments and all are done in constant time.

Thus making your complexity O(n^2) in worst case.

sai
  • 434
  • 5
  • 13
  • Good way to explain. – hagrawal7777 Apr 23 '17 at 20:31
  • int count=0; for(int i=0;i – raju Apr 23 '17 at 20:32
  • Time complexity will be number of times the loop is repeated, In worst case we assume loop to iterate till last item until element is reached. So it would be O(length of A) – sai Apr 23 '17 at 23:28
  • so if have a array of (N x M) the time complexity will be of O(NxM)?? this is what you were saying. – raju Apr 24 '17 at 23:59
  • If you have an 2d array with n rows and m columns, and you traverse each item ones, then it would be O(N*M). This might be useful http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm – sai Apr 25 '17 at 14:42