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

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'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?

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.

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..

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*.

Similar Questions

I need to write asm function in Delphi to search for max array element. So that wat I wrote. Got few prolbems here. First - mov ecx, len just dosen't work in right way here. Actually it replaces valu

Given a Sorted Array which can be rotated find an Element in it in minimum Time Complexity. eg : Array contents can be [8, 1, 2, 3, 4, 5]. Assume you search 8 in it.

Can any one explain why the time complexity for generating a binary heap from a unsorted array using bottom-up heap construction is O(n) ? (Solution found so far: I found in Thomas and Goodrich book t

From wikipedia: Sorted list implementation: Like a checkout line at the supermarket, but where important people get to cut in front of less important people. (O(n) insertion time, O(1) get-next tim

This one work: arr[0]=XX1 1 arr[1]=XX2 2 arr[2]=XX3 3 arr[3]=XX4 4 arr[4]=XX5 5 arr[5]=XX1 1 arr[6]=XX7 7 arr[7]=XX8 8 duplicate() { printf '%s\n' ${arr[@]} | sort -cu |& awk -F:

in a general binary search, we are looking for a value which appears in the array. Iometimes, we need looking for the first element that is greater/less than a target. Here is a binary search code wit

I want to insert an element into the right place that order maintains in the sorted list. I allocated 2*n size for the array and filled the rest with 999 since they are not used currently. ordered_ins

What is the complexity of search in sorted std::list? I knew that complexity of search in sorted data is O(log n) if the data structure has random access. But since list doesn't have random access, wh

I was just wondering what is the time complexty of merging two sorted arrays of size n and m, given that n is always greater than m. I was thinking of using merge sort, which I assume in this case wi

How to find duplicates in the array. In the case of the inverse problem when you have to find a unique element of all is clear you just xor all the elements and as a result we obtain a unique element.

I have two <span>s. First is font-size: 14px; and I want to reduce font-size of child <span> for 2 px; <span>14px font <span>12px span</span></span> How to do this

I want to keep a sorted queue of items, where I want to be able to pop the item with the lowest value (a bit like std::priority_queue). The item values are contiguous and ever increasing. However, the

I have a sorted array of 30 real numbers. The numbers are spread evenly. I want to search a number in this array. Currently, I am using linear search algorithm. In order to increase performance of my

I have a sorted array of length n and I am using linear search to compare my value to every element in the array, then i perform a linear search on the array of size n/2 and then on a size of n/4, n/8

I found the Time complexity of Prims algorithm everywhere as O((V + E) log V) = E log V. But as we can see the algorithm http://s28.postimg.org/iq2s43agd/image.png It seems like the time complexity is

We have two sets A, B and we want to compute set difference A - B, we will sort first elements of B with quicksort which have average complexity O(n * log n) and after we search each element from A in

Given a sorted array of integers, can we build a sorted array of the sums of all pairs in O(n^2)? A trivial solution would be to build the array of sums in O(n^2) and then to sort it in O(n^2 (log(n^2

Assume algo(p) is an algorithm that take Theta(p) time to execute and does not change p. Determine the running time complexity of the following algorithm: Algo2(n) begin p=1; while p <= n begin alg

I was wondering about the time complexity of the shuffle algorithm in the random python library/module. Is it O(n) or is it less than that? Is there a website that shows the time complexities of funct

How to find 'n' largest element positions in a 2D array ? Is there a good algorithm, other than brute force ? Thank you

Given an 2-D Array of n*n elements: all rows are sorted all columns are sorted For example: 1 5 7 2 6 8 3 9 10 convert it to a 1-D sorted array. Is there a solution better than O(nlog(n)).

This question already has an answer here: Algorithm: how to find a column in matrix filled with all 1, time complexity O(n)? 5 answers I'm dealing with some problematic complexity question via

I jave a 2D array like this, just like a matrix: {{1, 2, 4, 5, 3, 6}, {8, 3, 4, 4, 5, 2}, {8, 3, 4, 2, 6, 2}, //code skips... ... } (The Array is not sorted) I want to get all the 4 position, inste

Let's say we have this sorted array 0 1 1 1 1 2 2 2 2 2 3 10 10 10 I would like to find efficiently the positions where an element changes. For example in our array the positions are the following:

In all references on LDAP search filter operator I find <= for less than or equal to and >= for greater than or equal to. Is there really no strictly less than operator? Must I write attri

Gaussian elimination algorithm in transform and conquer has O(n3) complexity. Is there any technique that give more efficient complexity of this algorithm?

I read that the computational complexity of the general convolution algorithm is O(n^2), while by means of the FFT is O(n log n). What about convolution in 2-D and 3-D? Any reference?

Am I correct in my explanation when calculating the time complexity of the following algorithm? A HashSet, moduleMarksheetFiles, is being used to add the files that contain the moduleName specified.

How do I implement a sorted array into a binary search tree and find the Max depth. I can do each step separately but I am having trouble implementing them together. How would you implement an algorit

I am do a comparison based analysis of mergesort algorithm which outputs in ascending order. I notice it is faster (has less comparisons) when i give it a reverse sorted list instead of a ascending or

I recently encountered an algorithm for searching for numbers in a sorted list and this is how it goes: Given: An oracle that tells you if a given number greater than or less than the number being sea

I need to solve for the average case complexity of ternary search. In the worst case you would do two comparisons so I assume worst case complexity looks like this: C(n) = C(n/3) + 2 which can then b

What is the complixety of turning a sorted array of size n to a legal 2-4 B tree? What would it be if the array wasn't sorted. I believe that the first answer should be O(logn) (As many splits that we

I suspect there is a way if you can save by locating the other end of a range of repeated values faster than by iterating through that sublist

i want to select element that its index is greater than 3 and less than 6 ex: $(td:gt(3)) and $(td:lt(6)) ?

I need to have objects sorted by price (decimal) value for fast access. I need to be able to find all objects with price more then A or less than B. I was thinkg about SortedList, but it does not prov

By which I mean a structure with: O(log n) complexity for x.push() operations O(log n) complexity to find an element O(n) complexity to compute list(x) which will be sorted I also had a related ques

Can anybody optimize following statement in Scala: // maybe large val someArray = Array(9, 1, 6, 2, 1, 9, 4, 5, 1, 6, 5, 0, 6) // output a sorted list which contains unique element from the array with

I want to discuss an algorithm here which I found in a data structure book. This book presents a sketch of the algorithm to find the majority element (appears more than N/2 ) in an array of size N . T

I have this array (A) with n elements that are guaranteed to be sorted and I need to perform a binary search on them in a parallel system. I started off by making this binary search algorithm. It's it

As a thought exercise, I am trying to think of an algorithm which has a non-monotonic complexity curve. The only thing I could think of was some algorithm with asymptotic solution in extremities. Is t

I have to search array element values similar to mysql like. Array is as follows. $arraydata= array (0=> array('data'=>1), 1=> array('data'=>'1|5'), 2=>array('data'=>'2|3'), 3=>ar

There is a sorted array which is of very large size. In it every element is repeated more than once except one element. How can I find the unrepeated element in O(log n) time complextiy.

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O (log (m+n)). double findMedianSortedArrays(int

Here is another interview question Array contains elements where next element can be either x+1 or x-1 if previous element is x. Prev element = x Next element = x+1/ x-1 Example: {2, 3, 4, 3, 2, 1, 0

I know the complexity is O(nlog(n)). But why? How do you come to this answer? Any help would be much appreciated, I'm very interested to know!

I have some problem with removing an element from a sorted array (all instances of an element must be removed). When I run my program, I get a segmentation fault. I have no idea why that happens, beca

Is there a easy way to search in an array like this? Some examples below : 5 6 7 8 19 45 21 32 40 // Rolled over at 7 th element 15 22 32 45 121 341 40 // Rolled over at 7 th element 1 22 32 45 121 34

In a typical dynamic array implementation, we double the stack when there is no room for a new element. In this case of doubling the average time for push operation is O(n). What is the complexity of

While going through Time complexity of algorithm I came across O(log log n). I just want to know any well known algorithm having this complexity or a piece of code is appreciated to understand this ti