0

i am writing 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.

here i want the time complexity to be O(logN).

public static int FindPosition(int[] Arr, int element)
{
    int i; int u=0;
    {
        for(i=0;i<Arr.length;i++)
        {
            if(element>Arr[i])
            u++;
        }
    }
    return u;
}

does this program have time complexity of O(log n). can any one help me with changes to function so it can be in o(log n).

user7799918
  • 55
  • 1
  • 1
  • 6
  • It's O(n). You want binary search. It's linear search. And you can stop the loop once element <= Arr[i]. – xiaofeng.li Apr 20 '17 at 00:57
  • suppose you refer this [post](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) to get a understanding on how to calculate time complexity. – Rajith Pemabandu Apr 20 '17 at 01:00

1 Answers1

1

No.

That code iterates (worst case) over all the values in the array. If values are randomly inserted the insertion point will average to be the middle of the array. You don't break the loop when you find the location, as @LukeLee points out, so you will always iterate over every possible location - all N of them.

In order to get to O(logN) performance, you will have to skip lots of comparisons. Look into a binary search, if your array is ordered.

aghast
  • 14,785
  • 3
  • 24
  • 56