21
$\begingroup$

Given a sorted array of $n$ positive integers, the problem is to find the longest subsequence so that the progression of differences between consecutive elements of the subsequence is geometrically increasing.

Is there any complexity theoretic reason to believe this simple looking problem cannot be solved in $O(n^2)$ time?

added How fast can this problem be solved? Dynamic programming seems to give $O(n^3)$ time.

$\endgroup$
  • 1
    $\begingroup$ Can't we reduce this to longest arithmetically increasing subsequence? $\endgroup$ – Kaveh Aug 24 '13 at 7:05
  • 5
    $\begingroup$ @Kaveh How? Taking logs does not appear to help. Remember a subsequence looks like start, start+a, start+a r, start +ar^2 etc. $\endgroup$ – oxbowlake Aug 24 '13 at 7:08
  • 1
    $\begingroup$ It seems to me that a similar algorithm to the arithmetic case would work for this one. What is the motivation for this question by the way? I.e. why are you interested in it? $\endgroup$ – Kaveh Aug 24 '13 at 7:11
  • 2
    $\begingroup$ This note may be helpful. There are essentially no lower bounds known for this kind of problem. $\endgroup$ – Jeffε Aug 24 '13 at 20:09
  • 5
    $\begingroup$ @Kaveh the problem is that the "obvious" reduction to finding an AP (guess the first element and then take logs) would take $n^3$ time. I think that's what the OP wants to improve on. $\endgroup$ – Suresh Venkat Aug 25 '13 at 17:55

Your Answer

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

Browse other questions tagged or ask your own question.