i have coded an algorithm for search in sorted array with complexity log2(n)/5 .Is it useful?
views:
691answers:
6
+12
A:
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.
shoosh
2009-02-13 06:33:43
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
2009-02-13 08:41:21
you seem to have a slight misconception on what is exactly complexity.
shoosh
2009-02-13 20:50:50
+2
A:
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?
Imran
2009-02-13 06:57:07
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
2009-02-13 08:46:05
In that case there are O(loglogn) algorithms. See: http://www.dcc.uchile.cl/~rbaeza/ftp/tour.ps.gz
Imran
2009-02-13 09:23:54
+1
A:
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.
MSN
2009-02-13 07:01:59
+3
A:
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..
Nils Pipenbrinck
2009-02-13 13:39:33
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
2009-02-16 11:11:04
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.
Maddy.Shik
2009-02-16 12:01:07
+1
A:
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.
Daniel
2009-02-13 13:47:26
A:
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
Maddy.Shik
2009-02-16 12:03:26