2
$\begingroup$

I am aware that to get a running time by recursion tree method, we need to draw a tree and find:

a) number of levels in tree.

Since left side of tree decreases by 1 in size, so it's longest path from root. Subproblem size at level i is n-i . setting n - i = 1 when it hits a size of 1, we get number of levels, i = n - 1.

b) cost per node in tree : cn

c) Number of nodes at level i: This is where i am stuck. Not able to find nodes at level i since left side decreases by 1, right side by half. Naturally, tree is more dense towards left side. Not every node will have two children.

if i can get answer to c, i can calculate T(n) = cost of level 0 + cost of level 1 + cost of level 2 + ... cost of level n-1. if y1 is number of nodes at level 1, y2 at level 2, etc... then
=> T(n) = cn + y1 * cn + y2 * cn + y3 * cn + .... yn-1 * cn to get total cost.

Can anyone guide me to the approach i am taking ? is it correct ? can i take an assumption that for sufficiently large n, we can ignore T(n/2) and then proceed ? .

Online searching confused me. Problem is 4.4-5 from CLRS.

Please see here

This solution says T(n) = O(2^n) and T(n) = omega(n^2) and does not explain how.

Also see here

This solution says T(n) = O(n^2). but contradicts with above solution

$\endgroup$
2
  • $\begingroup$ It's a lovely problem. The T(n/2) is what makes it so nice, and it can absolutely not be ignored. Assume T(n) ≈ c n^k. Then T(n) ≈ c (n-1)^k + c (n/2)^k ≈ c (1 +2^-k)n^k - c n^(k-1) >> T(n). So the solution is not polynomial. $\endgroup$
    – gnasher729
    Commented Apr 23, 2020 at 23:19
  • $\begingroup$ The problems you quote are all different. It's very difficult to get an idea by looking at the formula only. (Well, Yuval can... ) Using a spreadsheet it looks like T(n) = n ^ f(n), where f(n) is a quite slowly growing function. If T(1) = 1 then T(n) ≈ n^3 for n around 130 or so, T(n) = n^2.5 for n around 38. $\endgroup$
    – gnasher729
    Commented Apr 23, 2020 at 23:24

2 Answers 2

6
$\begingroup$

Let $S(n) = T(n) - 2n - 2$. You can check that $S(n) = S(n-1) + S(n/2)$ (ignoring the fact that $n/2$ need not be an integer). This shows that the additive $n$ term doesn't make a big difference.

For large $n$, we have roughly $S(n) - S(n-1) \approx S'(n)$, and so we are led to solve the differential equation $$ S'(n) = S(n/2). $$ Consider $f(n) = \exp (\tfrac{1}{2}\log_2^2 n)$. Then $$ f'(n) = \exp (\tfrac{1}{2}\log_2^2 n) \cdot \frac{\ln n}{(\ln 4)n}, $$ whereas $$ f(n/2) = \exp(\tfrac{1}{2} (\log_2 n - 1)^2) \approx \exp(\tfrac{1}{2}\log^2 n) \exp(-\log n) = \exp(\tfrac{1}{2} \log^2 n) \cdot \frac{1}{n}. $$ This suggests that, at the very least, $\ln S(n) = \Theta(\log^2 n)$.

Where does this come from? You can think of $S(n)$ (with an appropriate base case!) as the number of ways to go from $n$ to zero by applying two operations: subtract 1 and divide by 2. A "typical" such sequence will contain roughly $\log_2n$ many operations of the second type, out of $\Theta(n)$ operations in total, leading to the very rough estimate $\binom{\Theta(n)}{\log_2 n}$, which is also of the form $\exp \Theta(\log^2 n)$.


Consider for concreteness the following precise definition of $S(n)$: the base case is $S(0) = 1$, and for $n > 0$, $$ S(n) = S(n-1) + S(\lfloor n/2 \rfloor). $$ This is sequence A000123. Knuth, An almost linear recurrence, showed that $$ \log_4 S(n) \sim \log_4^2 n, $$ that is, the ratio of the two terms tends to 1 as $n \to \infty$. The OEIS entry contains even more precise asymptotics.

$\endgroup$
4
  • $\begingroup$ I find exp (log^2 n) hard to imagine, but its the same as (exp (log n)) ^ log n = n^(log n). So it's a power of n, with a slowly growing exponent. $\endgroup$
    – gnasher729
    Commented Apr 23, 2020 at 23:29
  • $\begingroup$ @Yuval Thanks for the response. how do you conclude S(n) - S(n-1) = S'(n) ?. Sorry if it's lame, I am a beginner in CS theory. Also how did you come up with f(n) = exp(1/2 log^n ) ? . why this particular function ? $\endgroup$
    – sherelock
    Commented May 2, 2020 at 8:42
  • $\begingroup$ The mean value theorem states that for a nice enough function, $S(n) - S(n-1) = S'(n+\theta)$ for some $\theta \in [0,1]$. If $n$ is large then $S'(n+\theta) \approx S'(n)$, for some meaning of $\approx$. $\endgroup$ Commented May 2, 2020 at 8:51
  • $\begingroup$ I came up with $f(n)$ by trial-and-error. With more trial-and-error, it should be possible to come up with an even better solution. $\endgroup$ Commented May 2, 2020 at 8:52
-2
$\begingroup$

I disagree with the Fibonacci hypnosis, but I'm not hundred percent sure of my answer

You see $ T(n)= T(n-1) +c*n = O(n ^2) $

$ T(n) = T(n/2) + c*n =O(n log n) $

However, u don't get ur T(n) by straightforward adding.

If u go one level in the recursion (u can draw a tree)

T(n) =T(n-2) +T((n-1)/2) +T(n/2-1)+ T(n/4) + [n + (n-1) + (n-1)/2 + (n/2-1) +n/4]

This to show u it is also not just $ O(n^2) $

I have to complete it, but I suspect either $ O((n^2) * log n) $ or $ O((n^2) * n ^ {log n} ) = O(n^3) $

{There is a term n(1+1/2+1/4+..1/n) that decays in log n steps, I have to check again}

$\endgroup$
1
  • $\begingroup$ You are right, I'm very sorry. I'll edit my answer, or maybe delete it temporarily. $\endgroup$
    – ShAr
    Commented Apr 23, 2020 at 21:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.