Home > Algorithms > Searching and Sorting

Searching and Sorting

June 16, 2012

Time Complexities :

Searching :

Linear Search :

The worst-case time for a Linear Search is always O(N)

Binary Search :

For Binary search the values should be in a sorted manner.

The worst-case time for binary search is proportional to log2 N: the number of times N can be divided in half before there is nothing left. Using big-O notation, this is O(log N)

Don’t use binary search in the sorted Linked List if data

Reason : Binary search relies on being able to access the kth item in a sequence of values in O(1) time. This is possible when the values are stored in an array, but not when they’re stored in a linked list. So binary search using a linked list would usually be much slower than sequential search.

 

Links : http://pages.cs.wisc.edu/~bobh/367/SORTING.html

Advertisements
Categories: Algorithms
%d bloggers like this: