3
$\begingroup$

I was reading an article on Longest Arithmetic Progression. The solution given has S(n)=$O(n^2)$. Can't I solve it in $O(1)$ space? To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater). When we found them we still keep on decreasing left and right to find llap (length of longest arithmetic progression). The other cases left are those where llap is even.. for them I will select i and (i+1)$^{th}$ element as my center two elements of AP and find elements on their right and left satisfying ap. T(n) will still be $O(n^2)$.

Is my approach correct?

$\endgroup$
  • 1
    $\begingroup$ This is the simple solution mentioned at the top of your link, which runs in cubic time. $\endgroup$ – Yuval Filmus Aug 1 '18 at 20:37
  • $\begingroup$ Why do you think the running time will be $O(n^2)$? In any case, many are often reluctant to check solutions here. If you're unsure, your best bet is to try to prove your answer; or you can ask about some specific aspect you're unsure about. $\endgroup$ – D.W. Aug 1 '18 at 21:11
2
$\begingroup$

No, your approach is wrong. Consider the set of numbers $1, 3, 4, 6, 7, 8, 10$. The longest arithmetic progression(LAP) in it is $1, 4, 7, 10$, which is of even length. However, 4 and 7 are not adjacent items so your approach will not find that LAP.

Yes, your approach is correct, but to a different problem from the problem in the article you mentioned.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.