17

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.

Simd
  • 3,902
  • 20
  • 49
  • 1
    Can't we reduce this to longest arithmetically increasing subsequence? – Kaveh Aug 24 '13 at 07:05
  • 5
    @Kaveh How? Taking logs does not appear to help. Remember a subsequence looks like start, start+a, start+a r, start +ar^2 etc. – Simd Aug 24 '13 at 07:08
  • 1
    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? – Kaveh Aug 24 '13 at 07:11
  • 1
    @Kaveh I can't see a straightforward way to make the standard dynamic programming method take $O(n^2)$ time. The problem is that you need three, not two, points to define a subsequence. My interest is mostly just theoretical. I hope that is OK. – Simd Aug 24 '13 at 07:14
  • What is the fastest known solution for this problem? – Simd Aug 24 '13 at 10:40
  • 2
    This note may be helpful. There are essentially no lower bounds known for this kind of problem. – Jeffε Aug 24 '13 at 20:09
  • Thank you for the link to the note. However, does it say anything about my problem? I don't see a reduction from one problem to the other. Is there one? For lower bounds, I would be interested in one for my problem in a restricted model as well if it exists. – Simd Aug 25 '13 at 07:53
  • 5
    @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. – Suresh Venkat Aug 25 '13 at 17:55
  • your sequence is [n1, n2, n3, n4]= [s, s+a,s+a r, s+a r^2]. Consider [n32,n42,n43]=[n3-n2, n4-n2,n4-n3]= [a(r-1), a(r+1)(r-1), a r (r-1) ]. n42/n32=r+1, n43/n42=r, which is easy to check. That directly translates to algorithm pointed by JeffE (except you may need to keep a and r in the lookup table L). Plus you need to check that 's' is in the sequence - another log(n). Seem to be n^2 log n. Actually you can check it at the last moment for each longest candidate, so seem to be O(n^2). – mkatkov Jan 12 '16 at 21:41
  • @Jeffε, the link to “this note” seems to just go to your homepage. Are you able to update it? thanks. – kodlu Dec 27 '20 at 03:23
  • 1
    @kodlu Here is an updated link. – Jeffε Jan 03 '21 at 03:29

0 Answers0