i have coded an algorithm for search in sorted array with complexity log2(n)/5 .Is it useful?
0
Add a comment
|
5 Answers
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.
2 Comments
Maddy.Shik
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.
shoosh
you seem to have a slight misconception on what is exactly complexity.
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..
answered Feb 13, 2009 at 13:39
Nils Pipenbrinck
86.7k33 gold badges157 silver badges224 bronze badges
2 Comments
Maddy.Shik
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
well i had asked this question to see if my algo is new one or not.and from ur help i have found that its just interpolation search.
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?
2 Comments
Maddy.Shik
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
Imran
In that case there are O(loglogn) algorithms. See: dcc.uchile.cl/~rbaeza/ftp/tour.ps.gz
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.
Comments
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.
