17
$\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.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Can't we reduce this to longest arithmetically increasing subsequence? $\endgroup$
    – Kaveh
    Aug 24, 2013 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$
    – Simd
    Aug 24, 2013 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, 2013 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, 2013 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, 2013 at 17:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.