Solution to (a) Given an array A of integers, sorted into ascending order, design an efficient algorithm … - Sikademy

Nov. 28, 2020

Archangel Macsika Sikademy Image

Archangel Macsika

(a) Given an array A of integers, sorted into ascending order, design an efficient algorithm for finding is there is any array subscript i where A[i] == i. What is the worst case run time of your algorithm (in 'Big-Oh' notation)? (b) Do the same for an array A of non-negative integers, sorted in ascending order. What is the worst case run time of your algorithm (in 'Big-Oh' notation)?

Answer to: Given an array A of integers, sorted into ascending order, design an efficient algorithm for finding is there is any array subscript i where A[i] == i. What is the worst case run time of your algorithm (in "Big-Oh" notation)?

Here we have numbers that can be negative and positive, and they are sorted.

We binary search on the array, looking for A[i]==i we can use the fact that they are sorted to decide which half to throw away each test.

This approach works if we allow duplicates, or if all elements are unique values.

O(log N) for N elements in the array

Answer to: Do the same for an array A of non-negative integers, sorted in ascending order. What is the worst case run time of your algorithm (in "Big-Oh" notation)?

We have two situations.

First situation: there are no duplicates.

We now have sorted unique integers and the smallest possible element is 0.

So we check to see if A[0]==0.

If so, then there is some A[i]==i (at least 0, possibly more but we did not need to find them all... we just need to answer "is there some i".

If A[0] is not 0 then there can be no other A[i]==i.

O(1) worst case complexity.

Second situation: there are duplicates.

Here we have 0 as the lowest possible element, but we can also have sequences of the same element in places in the array.

Now, checking simply for A[0]==0 is not enough...

For example, if all elements in the array are 7, then A[0] is not 0, but A[7] is 7.

So we are back to doing binary search to find the answer.

O(log N) worst case.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers