CODEWITHSUNDEEP
javaarraystime-complexityruntime-compilation
user7799918
user7799918

Reputation: 55

time complexity for array insertion

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).

Upvotes: 0

Views: 621

Answers (1)

aghast
aghast

Reputation: 15300

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.

Upvotes: 1

Related Questions