CODEWITHSUNDEEP
algorithmsearchtime-complexity
Maddy.Shik
Maddy.Shik

Reputation: 6787

Is there any algorithm for search an element in sorted array with complexity less than log2(n)

i have coded an algorithm for search in sorted array with complexity log2(n)/5 .Is it useful?

Upvotes: 0

Views: 2246

Answers (5)

Daniel
Daniel

Reputation: 1251

I think it would be useful if it is faster than other existing O(logn) search algorithms in practice. In other words, if your benchmark testing shows speed improvements. However, for very large inputs constant time improvements (like 1/5) don't make much of a difference. That's why most importance is given to an algorithm's asymptotic complexity.

Upvotes: 1

Nils Pipenbrinck
Nils Pipenbrinck

Reputation: 86443

Hm. Tough question. Why don't you post your algorithm and let us see what you do.

However, for a real win you should be better than O(log2 log2 (n))? That's what interpolation search does on average..

http://en.wikipedia.org/wiki/Interpolation_search

Upvotes: 4

Imran
Imran

Reputation: 13478

It's not possible to do better than log₂n without any other assumptions about the array other than that it's sorted, or without any precomputation / data structure creation.

How do you propose to terminate in less than log₂n steps if the element you are looking for is not in your array?

Upvotes: 2

MSN
MSN

Reputation: 54634

Of course, you can always argue about whether or not a non-linear search is necessarily faster than a linear search: http://www.ddj.com/184405848

I.e., if you are searching a cache line, it can be faster to search it linearly than branching.

Upvotes: 1

shoosh
shoosh

Reputation: 79021

It is provable that you can't get lower than O(log(n)) for a search that assumes only compare operations. a complexity of log2(n)/5 is the same thing as O(log(n)).
Usefulness depends on what you use it for.

Upvotes: 12

Related Questions