# no. of comparisons in linear/binary search

• 06-05-2004
alice
no. of comparisons in linear/binary search
hi, what is the no. of comparison in a worst case unsorted one-dimensional array of size N with linear search?

is it 'N'?

and if worst case sorted one-dimensional array of size N with binary search,

is it (log N / log2) ?

but what is best case in binary search?
• 06-05-2004
CompiledMonkey
Quote:

Originally Posted by alice
hi, what is the no. of comparison in a worst case unsorted one-dimensional array of size N with linear search?

is it 'N'?

and if worst case sorted one-dimensional array of size N with binary search,

is it (log N / log2) ?

but what is best case in binary search?

I dunno if I'm right, but I'll try.

worst case for linear search: n
worst case binary search: log n
best case binary search: 1 (assuming it found the result on the first attempt)
• 06-05-2004
vsriharsha
Well, just to add a small element....
You refer to the order by the Big O notation.
Order for Linear Search is: O(n)
and order for Binary Search is: O(log n).

Cheers,
Harsha.
• 06-05-2004
Thantos
Worse case is log n / log 2 rounded up to the next whole integer.

So: 8,000,000 elements would require at most 23 searches.
• 06-05-2004
CompiledMonkey
Quote:

Originally Posted by vsriharsha
Well, just to add a small element....
You refer to the order by the Big O notation.
Order for Linear Search is: O(n)
and order for Binary Search is: O(log n).

Cheers,
Harsha.

I thought that was a given. :D
• 06-05-2004
alice
then what is
Worst case unsorted two-dimensional array of size N with linear search &
Best case unsorted two -dimensional array of size N with linear search?

I think the first one is log(NxN) / log 2 ?
but what is the second one? I haven't any idea.

thk a lot.
• 06-05-2004
CompiledMonkey
Wouldn't the array be setup in such a way that you're only searching one of the two columns? Even if you did have to look at each column, I imagine you're looking at O(2n). I'm not sure about that though. Best case could be O(1) in any search.
• 06-05-2004
Thantos
Quote:

Originally Posted by alice
Worst case unsorted two-dimensional array of size N with linear search &
Best case unsorted two -dimensional array of size N with linear search?

Worse case for unsorted arrays is always the number of elements, since the only way to search an unsorted array is by linear search.