time complexity for array insertion

Question

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

It's O(n). You want binary search. It's linear search. And you can stop the loop once element <= Arr[i]. — xiaofeng.li
– xiaofeng.li, Commented Apr 20, 2017 at 0:57
suppose you refer this post to get a understanding on how to calculate time complexity. — Rajith Pemabandu
– Rajith Pemabandu, Commented Apr 20, 2017 at 1:00

aghast · Accepted Answer · 2017-04-20 01:01:32Z

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.

edited Apr 20, 2017 at 1:01

answered Apr 20, 2017 at 0:57

aghast

15.4k4 gold badges31 silver badges58 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

xiaofeng.li Over a year ago

Unfortunately the code iterates over all the elements no matter what.

Collectives™ on Stack Overflow

time complexity for array insertion

1 Answer 1

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Linked

Related