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

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.

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.

This algorithm works for list of random numbers . I have given test data of 5,20,000 random numbers . So I think it can be useful in every problem and some times in case of small numbers list its complexity is just close to constant complexity.

– Maddy. Shik Feb 13 '09 at 8:41 1 you seem to have a slight misconception on what is exactly complexity. – shoosh Feb 13 '09 at 20:50.

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.. en.wikipedia.org/wiki/Interpolation_search.

Sir , I think it is just close to log2(log2(n)). But I cant prove it mathematically. I have done it on random data of size like(10,100,1000,10000 up to 512000).

And mo of operations are log2()of no of operation in binary. It is based upon assumption that numbers are on constant gap like(5,10,15,20,25) – Maddy. Shik Feb 16 '09 at 11:11 well I had asked this question to see if my algo is new one or not.

And from your help I have found that its just interpolation search. – Maddy. Shik Feb 16 '09 at 12:01.

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?

This algorithm works for list of random numbers . I have given test data of 5,20,000 random numbers . So I think it can be useful in every problem and some times in case of small numbers list its complexity is just close to constant complexity.In case number is not present complexity is better oflog2n – Maddy.

Shik Feb 13 '09 at 8:46 In that case there are O(loglogn) algorithms. See: dcc.uchile.Cl/~rbaeza/ftp/tour.ps. Gz – Imran Feb 13 '09 at 9:23.

Of course, you can always argue about whether or not a non-linear search is necessarily faster than a linear search: ddj.com/184405848 I.e. , if you are searching a cache line, it can be faster to search it linearly than branching.

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.

Algorithm I have made is interpolation search(linear). I thought it is new one . Bt finally I got it that it already exists.

Thanks to stackoverflow.com.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.