Generalizing a simple linear-time algorithm

Question

I am trying to write a linear-time algorithm O(n), which given a table A[0..n-1] (filled with ascending natural values) checks if there is a pair A[i], A[j] which satisfies f(A[i], A[j]) = C (C is a predefined constant).

Supposing that f(a,b) = a+b the algorithm will be:

Algo Paires(A[0..N-1], C)
in: Tab A[0..n-1] and C a constant
out : Boolean
Init indice ← 0
For i ← 0..n-1 do 
    if indice ≠ i & A[indice] + A[i] = C 
      return true
    else if i = n-1 & indice ≤ n-2 
      indice++; i ← 0;
End for
return False

But if:

enter image description here

what will be the algorithm then? any suggestions ?

I'm just looking for some help and i think that i'm in the right place... i wrote the algo myself & now i want to generalize it but unfortenaly i cant figure out how ... i dont want you do to it for me but help me with some hints or suggestions.... — Mooh, Mar 14 '11 at 19:26
It iterates n times on `indice`, and in each iteration it iterates n times on `i`. — aaz, Mar 14 '11 at 19:39
hmmm that's true :/ any suggestion on how to change the execution time to O(n) ? — Mooh, Mar 14 '11 at 19:45
@aaz: Sorry, I voted up Mooh's comment, but now that I actually look at the solution, I see that you are correct; it is O(n²). @Mooh: However, it can still be done simply in O(n) *(hint: one method requires two indicies, which do not both start at 0...)* — BlueRaja - Danny Pflughoeft, Mar 14 '11 at 19:47
The structure is roughly correct, which is why it looks like O(n), but `i` shouldn't need to be reset to 0. — aaz, Mar 14 '11 at 19:57

score 7 · Accepted Answer · answered Mar 14 '11 at 19:20

7

Hint: Suppose there is a 2D matrix whose rows and columns are sorted and you are given a number x which you need to find...

answered Mar 14 '11 at 19:20

It doesn't seem like we're looking for a linear algorithm anymore because both this answer and the pseudo code in the example are quadratic. Given that, we can do calculate the answer in O(1) space right? – efficiencyIsBliss Mar 15 '11 at 00:13
@efficieny: Why do you think this is quadratic? – Mar 15 '11 at 00:54
@efficiencyIsBliss: As I mentioned above, though the pseudo-code is quadratic, it can certainly be done in linear-time (so can this). – BlueRaja - Danny Pflughoeft Mar 15 '11 at 22:47
@Moron In order to determine if there is such a pairing, don't we have to(in the worst case) compute all the entries in the 2D array? – efficiencyIsBliss Mar 16 '11 at 00:01
@BlueRaja I read your comments and I agree that the pseudo-code can be done in linear time, though I can't seem to figure out how this can also be done in linear time. – efficiencyIsBliss Mar 16 '11 at 00:04
@Moron My mistake, I'd forgotten the part about the array being sorted. – efficiencyIsBliss Mar 16 '11 at 02:01

Generalizing a simple linear-time algorithm

1 Answers1