<p>I have a recursive algorithm in which the time for each step depends on the time for smaller steps. Essentially a structure is built at steps 1, 2, ..., n which must be searched at larger heights:</p>

<p>$$
T(n)=T(n-1)+(1+o(1))\log(T(n-1))
$$</p>

<p>(yes, the larger the time searching the more data is added to the structure!)</p>

<p>It seems 'obvious' that $T(n)\approx n\log n,$ but can this be proved? In particular:
$$
T(n)\stackrel{?}{=}n\log n+o(n\log n)
$$</p>

<p>Better bounds on the error term would be great. I believe the error is $\omega(n).$</p>

CC BY-SA 3.0
2012-09-13T18:18:47.727Z
When you have a recurrence that you think you know the correct solution to, it generally works to prove the solution by induction (replacing all big-O type notations with explicit constants, e.g. the 1+o(1) terms in your recurrence and in your proposed solution would be replaced by 1+epsilon or 1+delta for some epsilon and delta that your induction proof will help you quantify). Have you tried that?
David Eppstein
CC BY-SA 3.0
2012-09-13T18:49:20.340Z
given that what David suggested works very easily (or I haven't had enough coffee yet..) and also is the first thing you learn about bounding recurrences in analysis of algorithms, I think the question is much better fit for CS@SE. voting to close
Sasho Nikolov
CC BY-SA 3.0
2012-09-13T19:03:37.157Z
@SashoNikolov: I don't think it's as easy as you suggest, especially for the desired error term n log log n. In particular, since the extra work in each term depends on the last (rather than being a function of n), the errors can compound in nonobvious ways. Also I asked a pure-math version of the question (with references to analysis of algorithms removed) at math.se without getting an answer, even after offering a bounty. (Well, I got an informative response, just not one that answered the question.)
Charles
CC BY-SA 3.0
2012-09-13T19:40:19.577Z
@Charles, could you please give a link to the question on MSE?
Kaveh
CC BY-SA 3.0
2012-09-13T19:48:29.220Z
@Kaveh: It should be this one http://math.stackexchange.com/questions/176858/asymptotic-behavior-of-iterative-sequences
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2012-09-13T20:57:14.783Z
maybe i am misunderstanding your question. is there some issue in carrying out david's approach and getting $T(n) \leq n\log n + o(n\log n)$? or are you asking about bounds on lower order terms as well?
Sasho Nikolov
CC BY-SA 3.0
2012-09-13T22:14:45.580Z
@Charles: In your question, you never said that the desired error term is n log log n.  You should not expect that people can answer a question which you did not state!
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-14T05:18:58.560Z
In any case for more precise error control you need to specify $o(1)$.
Sasho Nikolov
CC BY-SA 3.0
2012-09-14T05:26:07.257Z
@SashoNikolov: If you can prove that (i.e., that for some choices of o(1) the error is not O(n log log n)) I'd accept it as an answer! o(1) is all I know about its behavior; it can act very strangely in fact.
Charles
<ds.algorithms><time-complexity><analysis-of-algorithms>
Tricky big-O calculation
Charles
# Tricky big-O calculation

(Asked by: username_0 on 2012-09-13)

I have a recursive algorithm in which the time for each step depends on the time for smaller steps. Essentially a structure is built at steps 1, 2, ..., n which must be searched at larger heights:

$$
T(n)=T(n-1)+(1+o(1))\log(T(n-1))
$$

(yes, the larger the time searching the more data is added to the structure!)

It seems 'obvious' that $T(n)\approx n\log n,$ but can this be proved? In particular:
$$
T(n)\stackrel{?}{=}n\log n+o(n\log n)
$$

Better bounds on the error term would be great. I believe the error is $\omega(n).$

**Tags:** ds.algorithms, time-complexity, analysis-of-algorithms

> **Comments:**
> **username_1**: When you have a recurrence that you think you know the correct solution to, it generally works to prove the solution by induction (replacing all big-O type notations with explicit constants, e.g. the 1+o(1) terms in your recurrence and in your proposed solution would be replaced by 1+epsilon or 1+delta for some epsilon and delta that your induction proof will help you quantify). Have you tried that?  
> **username_2**: given that what David suggested works very easily (or I haven't had enough coffee yet..) and also is the first thing you learn about bounding recurrences in analysis of algorithms, I think the question is much better fit for CS@SE. voting to close  
> **username_0**: @SashoNikolov: I don't think it's as easy as you suggest, especially for the desired error term n log log n. In particular, since the extra work in each term depends on the last (rather than being a function of n), the errors can compound in nonobvious ways. Also I asked a pure-math version of the question (with references to analysis of algorithms removed) at math.se without getting an answer, even after offering a bounty. (Well, I got an informative response, just not one that answered the question.)  
> **username_3**: @username_0, could you please give a link to the question on MSE?  
> **username_4**: @username_3: It should be this one http://math.stackexchange.com/questions/176858/asymptotic-behavior-of-iterative-sequences  
> **username_2**: maybe i am misunderstanding your question. is there some issue in carrying out david's approach and getting $T(n) \leq n\log n + o(n\log n)$? or are you asking about bounds on lower order terms as well?  
> **username_5**: @username_0: In your question, you never said that the desired error term is n log log n.  You should not expect that people can answer a question which you did not state!  
> **username_2**: In any case for more precise error control you need to specify $o(1)$.  
> **username_0**: @SashoNikolov: If you can prove that (i.e., that for some choices of o(1) the error is not O(n log log n)) I'd accept it as an answer! o(1) is all I know about its behavior; it can act very strangely in fact.  

---

## 0 answers

