CODEWITHSUNDEEP
arraysalgorithm
Johan S
Johan S

Reputation: 3591

Magic Array Index Time/Space Complexity

I've been looking at the following problem:

Magic Index: A magic index in an array A[0...n-1] is defined to be an index i such as A[i] = i. Given a sorted non-distinct array of integers, write a method to find a magic index if one exists.

Here is my solution:

static int magicNonDistinct(int[] array, int start, int end) {
  if (end < start) return -1;
  int mid = start + (end - start) / 2;
  if (mid < 0 || mid >= array.length) return -1;

  int v = array[mid];
  if (v == mid) return mid;

  int leftEnd = Math.min(v, mid - 1);
  int leftRes = magicNonDistinct(array, start, leftEnd);
  if (leftRes != -1) return leftRes;

  int rightStart = Math.max(v, mid + 1);
  int rightRes = magicNonDistinct(array, rightStart, end);
  return rightRes;
}

It works just fine and is the recommended solution from the book Cracking The Code Interview 6th Edition, problem 8.3 Follow up (sorry for spoiling).

However when running this on a distinct array with no magic index, it visits all the elements, yielding a worst case running time of O(n).

Since it is recursive it takes O(n) memory as worst case.

Why would this solution be preferable to just iterating over the array? This solution (my own) is better I would argue:

static int magicNonDistinctV2(int[] array) {
  for (int i = 0; i < array.length; ++i) {
    int v = array[i];
    if (v == i) return v;
    if (v >= array.length) return -1;
    else if (v > i) i = v - 1;
  }

  return -1;
}

O(n) running time O(1) space always?

Could somebody derive a better time complexity for the initial algorithm? I've been thinking about looking if it is O(d), where d is the number of distinct elements, however that case is also wrong since the min/max only works in one direction (think about if v = 5, mid = 4 and the lower part of the array is all fives).

EDIT:

Ok people think I'm bananas and scream O(log(n)) as soon as they see something that looks like binary search. Sorry for being unclear folks.

Let's talk about the code in the first posting I made (the solution by CTCI):

If we have an array looking like this: [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8], actually an array looking like this: [-1,...,n-2] of size n, we know that there is not element that can match. However - the algorithm will visit all elements since the elements aren't unique. I dare you, run it, it can not divide the search space by 2 as in a regular binary search. Please tell me what is wrong with my reasoning.

Upvotes: 4

Views: 1673

Answers (3)

EmDroid
EmDroid

Reputation: 6046

No, in my opinion the first solution is not O(log n) as other answers state, it is really O(n) worst case (in the worst case it still needs to go through all the elements, consider equivalence array shifted by one as also mentioned by the author).

The cause why it is not O(log n) is because it needs to search on both sides of the middle (binary search only checks one side of middle therefore it is O(log n)).

It allows to skip items if you're lucky, however your second iterative solution skips items too if not needed to look on them (because you know there cannot be magic index in such range as the array is sorted) so in my opinion the second solution is better (the same complexity + iterative i.e. better space complexity and no recursive calls which are relatively expensive).

EDIT: However when I thought about the first solution again, it on the other side allows to also "skip backwards" if possible, which the iterative solution does not allow - consider for example an array like { -10, -9, -8, -7, -6, -5 } - the iterative solution would need to check all the elements, because it starts at the beginning and the values do not allow to skip forward, whereas when starting from the middle, the algo can completely skip checking the first half, then the first half of the second half, etc.

Upvotes: 3

displayName
displayName

Reputation: 14389

  • You are correct, the worst case complexity is O(n). You may have to visit all the elements of your array.
  • There is only one reason to not visit the array elements [mid, end] and that is when array[mid] > end (because in that case, the magic index is surely absent from [mid, end] elements).
  • Similarly, there is only one reason to not visit the array elements [start, mid] and that is when array[start] > mid.
  • So, there is a hope that you may not have to visit all the elements. Therefore it is one optimization which may work.

Thus, this binary-like method seems better than iterating over the entire array linearly but in worst case, you will hit O(n).

PS: I've assumed that array is sorted in ascending order.

Upvotes: 2

Salvador Dali
Salvador Dali

Reputation: 222761

It looks like you misunderstood the time complexity the required solution. The worse case is not O(n), it is O(log(n)). This is because during each pass you search next time only half of the array.

Here is a C++ example and check that for the whole array of 11 elements, it take only 3 checks.

Upvotes: 0

Related Questions