<p>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.</p>

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

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

CC BY-SA 3.0
2013-08-24T07:05:38.643Z
Can't we reduce this to longest arithmetically increasing subsequence?
Kaveh
CC BY-SA 3.0
2013-08-24T07:08:06.657Z
@Kaveh How? Taking logs does not appear to help.  Remember a subsequence looks like start, start+a, start+a *r, start +a*r^2 etc.
Simd
CC BY-SA 3.0
2013-08-24T07:11:20.543Z
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
CC BY-SA 3.0
2013-08-24T07:14:47.143Z
@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
CC BY-SA 3.0
2013-08-24T10:40:17.360Z
What is the fastest known solution for this problem?
Simd
CC BY-SA 3.0
2013-08-24T20:09:16.603Z
[This note](http://www.cs.illinois.edu/~jeffe/pubs/arith.html) may be helpful.  There are essentially _no_ lower bounds known for this kind of problem.
Jeffε
CC BY-SA 3.0
2013-08-25T07:53:08.957Z
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
CC BY-SA 3.0
2013-08-25T17:55:29.387Z
@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
CC BY-SA 3.0
2016-01-12T21:41:34.420Z
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
CC BY-SA 4.0
2020-12-27T03:23:52.837Z
@Jeffε, the link to “this note” seems to just go to your homepage. Are you able to update it? thanks.
kodlu
CC BY-SA 4.0
2021-01-03T03:29:27.320Z
@kodlu Here is an [updated link](https://jeffe.cs.illinois.edu/pubs/arith.html).
Jeffε
<ds.algorithms>
Longest geometrically increasing subsequence
Simd
# Longest geometrically increasing subsequence

(Asked by: username_0 on 2013-08-24)

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.

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: Can't we reduce this to longest arithmetically increasing subsequence?  
> **username_0**: @username_1 How? Taking logs does not appear to help.  Remember a subsequence looks like start, start+a, start+a *r, start +a*r^2 etc.  
> **username_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?  
> **username_0**: @username_1 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.  
> **username_0**: What is the fastest known solution for this problem?  
> **username_2**: [This note](http://www.cs.illinois.edu/~jeffe/pubs/arith.html) may be helpful.  There are essentially _no_ lower bounds known for this kind of problem.  
> **username_0**: 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.  
> **username_3**: @username_1 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.  
> **username_4**: 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).  
> **username_5**: @username_2, the link to “this note” seems to just go to your homepage. Are you able to update it? thanks.  
> **username_2**: @username_5 Here is an [updated link](https://jeffe.cs.illinois.edu/pubs/arith.html).  

---

## 0 answers

