Quadratic Search

Quadratic Search

type568

Member #8,381

March 2007

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.

kazzmir

Member #1,786

December 2001

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
| 4
| 9
| 16
| 25

A linear algorithm would have a table more like

length | number of steps
| 2
| 3
| 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.

type568

Member #8,381

March 2007

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.

kazzmir

Member #1,786

December 2001

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

james_lohr

Member #1,947

February 2002

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.

kazzmir

Member #1,786

December 2001

Oh search, not sort. Whateva

type568

Member #8,381

March 2007

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

james_lohr

Member #1,947

February 2002

Search. Not sort.

Quote:

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

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

kazzmir

Member #1,786

December 2001

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

type568

Member #8,381

March 2007

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

Karadoc ~~

Member #2,749

September 2002

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

-----------

type568

Member #8,381

March 2007

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

Bob

Free Market Evangelist

September 2000

Quote:

I don't think there's such thing as a search with quadratic running time.

Clearly, you haven't use Outlook.

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

--
- Bob
[ -- All my signature links are 404 -- ]

Goalie Ca

Member #2,579

July 2002

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

-------------
Bah weep granah weep nini bong!

type568

Member #8,381

March 2007

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:

Quote:

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

Yeah, why not?

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