What is a "Quadratic Search", and what is it's runtime complexity on a one dimensional sorted array? And would would it be, in the best(o0) aka fastest case.

I'm asking, as it appeared to be not simple to find an answer by googling. All I could found, has pretty much nothing to do with computers.

Thanks.

Quadratic search means the algorithmic complexity a function takes to execute. Algorithmic complexity is a way to talk about how a function scales relative to its input.

For an input of X if the function looks at each element of X just once then you say the function is linear.
For an input of X if the function looks at each element of X for every element of X then the function is quadratic.

What I mean is if you had this loop

void func( int x[], int length ){
  int i, j;
  for ( i = 0; i < length; i++ ){
     for ( j = 0; j < length; j++ ){
        x[ ... ] = i + j;
     }
   }
}

It doesn't matter what goes into x[...], the point is the inner loop goes from 0..length for every number from 0..length. The number of total times x[...] is executed is length * length as you can see from this small table.

length | number of loops
2 | 4
3 | 9
4 | 16
5 | 25

A linear algorithm would have a table more like

length | number of steps
2 | 2
3 | 3
4 | 4

Which is much better.

A search algorithm that is quadratic is Bubble sort, although the wikipedia article mentions bubble sort is O(n) in the best case.

Thank you. What you have said, seems quite clear, and logical. Perhaps my question is an absurdity. But it claims, there's a search algorithm, called "quadratic search" which has it's own complexity.

Well, I've never heard of such a thing. Typically quadratic is used as an adjective when describing algorithms like "that search is quadratic" or "my function is slow because its quadratic".

kazzmir: I don't think that's what he is asking.

I don't think there's such thing as a search with quadratic running time. The worst case of any search is going to be linear, and likely have a log(n) average running time (e.g. binary search on a sorted list).

I think a quadratic search is probably some sort of mathematical method of fitting a quadratic to something... I have no idea though.

Oh search, not sort. Whateva

Heh, life sux. The worst case of a search is O(n* log n) though. (If searching not a sorted array)

Search. Not sort.

No it's not. Worst case on an unsorted array is O(n).

No, its O(n). You only have to look at each element once.

I am sorry, I confused it with sorting. :|

But I can manage to write an array search as n*log n, trust me on that

In other (probably unrelated) news, I find it particularly interesting that the best possible algorithm for searching an unsorted database with a quantum computer is O(sqrt(N)). Grover's algorithm achieves this limit. I think it's interesting both because it beats the classical limit of O(N), but also because it doesn't seem to beat it by much... and that sqrt smells of the ^2 that turns "amplitudes" into "probabilities". (if you don't know what I'm talking about, never mind. I'm kind of talking to myself.)

Qsort also turns into probabilities, though it's faster than merge.

Clearly, you haven't use Outlook.

As to the OP, do you mean a quadratic hash function?

Quadratic search made my head asplode.

Not in 1
Not in 1 or 2
Not in 1 or 2 or 3
Not in 1 or 2 or 3 or 4
...

I doesn't look for me, that we have studied hashing.. But perhaps.. T_T

I encountered something similar during my googling crusade. But, it was supposed to be a search. :|

Edit:

Yeah, why not?

Now, how to make an n*log n though..