4

I am trying to calculate the Big-Oh for this code, which is for performing a binary search on a linked list:

public int search( List<T> list, T target ) {

        int low = 0;
        int high = list.size() - 1;
        int middle;

        while ( low <= high ) {             // frequency << log( n )
            middle = ( low + high ) / 2;
            int cmp = target.compareTo( list.get( middle ) );   // time << n

            if ( cmp < 0 ) high = middle - 1;
            else if ( cmp > 0 ) low = middle + 1;
            else return middle;

        }   // time << n log( n )

        return -1;

}   // time << n log( n )

I get O(n log(n)) as the answer. Is this a correct way of calculating this search method for this type of list?

tomas
  • 245
  • 2
  • 10
  • Binary search is log n, not n log n. Look into this recurrence: http://stackoverflow.com/a/8185382/150818 – SJha Sep 21 '14 at 17:58
  • 1
    @SaketJha: No, you're assuming that the list-access-by-index operation is O(1), which it's not for a linked list. – Jon Skeet Sep 21 '14 at 17:58
  • 1
    @SaketJha, if u read the question properly, it says binary search on a linked list. and thats not O(log n) – Haris Sep 21 '14 at 17:59
  • 5
    Basically, using a binary search on a linked list is a bad idea... you'd be better off doing a linear scan, which is O(n). – Jon Skeet Sep 21 '14 at 17:59
  • I know it's not the best thing, but this is for an assignment where we are analyzing different algorithms. After what I can understand, get() for a LinkedList is O(n), so I thought n*log(n) would be the proper answer. – tomas Sep 21 '14 at 18:02

1 Answers1

-1

Third line from the while(),

list.get( middle )

is expensive for linkedList, it's O(n/2) average case == O(n) but for arrayList it is O(1) so eventhough the algorithm narrows to an element in O(log n), accessing the array elements in each loop is incuring O(n) to this giving you O(n log n).

I'm guessing if you pass ArrayList to the function, it will give you better performance. Give it a shot. Good that you implemented the function using List generic interface, you should be able to pass ArrayList.

And make sure you study the difference between arraylist and linkedlist in terms of access/indexing, read, write, search, clone operations...etc.

Rose
  • 2,792
  • 4
  • 28
  • 42