3

I understand that binary search cannot be done for an unordered array. I also understand that the complexity of a binary search in an ordered array is O(log(n)).

Can I ask

  1. what is the complexity for binary search(insertion) for an ordered array? I saw from a textbook, it stated that the complexity is O(n). Why isn't it O(1) since, it can insert directly, just like linear search.

  2. Since binary search can't be done in unordered list, why is it possible to do insertion, with a complexity of O(N)?

Spektre
  • 49,595
  • 11
  • 110
  • 380
overflowhow
  • 77
  • 1
  • 7

1 Answers1

0

insertion into list complexity depends on used data structure:

  1. linear array

    In this case you need to move all the items from index of inserting by one item so you make room for new inserted item. This is complexity O(n).

  2. linked list

    In this case you just changing the pointers of prev/next item so this is O(1)

Now for the ordered list if you want to use binary search (as you noticed) you can use only array. The bin-search insertion of item a0 into ordered array a[n] means this:

  1. find where to place a0

    This is the bin search part so for example find index ix such that:

    a[ix-1]<=a0 AND a[ix]>a0 // for ascending order

    This can be done by bin search in O(log(n))

  2. insert the item

    so you need first to move all the items i>=ix by one to make place and then place the item:

    for (int i=n;i>ix;i--) a[i]=a[i-1]; a[ix]=a0; n++;

    As you can see this is O(n).

  3. put all together

    so O(n+log(n)) = O(n) that is why.

BTW. search on not strictly ordered dataset is possible (although it is not called binary search anymore) see

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • 1
    Linear array is referring to binary search and linked list is referring to linear search? – overflowhow Apr 10 '16 at 10:16
  • for linked list insertion, isn't it complexity suppose to be O(n)? since although it's ordered, but it may insert at the last position – overflowhow Apr 10 '16 at 10:21
  • @overflowhow yep you're right but you are mixing insert and search operation they are two separate operations. See answer I reedited to match your question – Spektre Apr 10 '16 at 10:28