# Tag Info

## Hot answers tagged recurrence-relation

Accepted

### How to solve a recurrence relation with a sum?

Here are several ways to solve your recurrence relation. Guessing Anyone with enough experience in computer science might recognize your recurrence as the one satisfied by $T(n) = 2^n$. Given this ...
• 278k

• 4,511

### Solving or approximating recurrence relations for sequences of numbers

After checking this post again, I'm surprised this isn't on here yet. Domain Transformation / Change of Variables When dealing with recurrences it's sometimes useful to be able to change your ...
• 4,511
Accepted

### Solving or estimating the recurrence $T(n) = x + T(n-\log_2 n)$

Assuming an appropriate base case, it is easy to see that $T(n) \geq (n/\log_2 n) \cdot x$, since at each step we subtract at most $\log_2 n$, and thus it takes t least $n/\log_2 n$ steps to reach ...
• 278k
Accepted

### Recurrence relation of the coin change problem

For that recurrence to make sense, $V$ can only be the array that contains the coin values; that is, $V=\{C_1, C_2, ..., C_m\}$. Whenever confronted with a new dynamic programming problem, you should ...
• 3,744
Accepted

### Solving recurrence relation with square root

The answer cannot be $O(\log\log n)$. Already without applying any recursion we have the inequality $T(n) = T(\sqrt{n}) + n \ge n$. So the complexity cannot be smaller than $O(n)$. But now to your ...
• 1,585
Accepted

• 4,511
Accepted

• 9,877
Accepted

The standard technique is to notice that your recurrence is just Pascal's identity, and so $$T(n,k) = \binom{n}{k}$$ is a solution to the recurrence. There are other solutions, for example $T(n,k) = ... • 278k 6 votes Accepted ### The recursion$T(n) = T(n/2)+T(n/3)+n$If$T(1)\le 6$and$T(2)\le 12$, we can show that$T(n)\le 6n$by induction. $$T(n) = T(n/2) + T(n/3) + n \le 6(n/2)+ 6(n/3)+n= 6n.$$ More generally, let$c\gt6$be a constant such that$T(1)\le c$... • 39.1k 5 votes Accepted ### Solving recurrence relation$T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n$using method of guessing and confirm? The book answer skips over some things. Here's a more detailed explanation. You want to show$T(n)=O(n\log n)$, in other words there exists a$c>0$such that$T(n)\le c\cdot n\log n$. [Actually, ... • 14.9k 5 votes Accepted ### Solving Recurrence Relation (quicksort ) Your mistake is$2\mathcal{O}(n/2) = \mathcal{O}(n/2)$. More generally, in order not to be confused, it is much better to replace$\mathcal{O}(n)$with$An$for some constant$A$, which can be taken ... • 278k 5 votes Accepted ### Recurrence which cannot be analyzed by master theorem Suppose for simplicity that$n$is a power of 2. Construct the tree corresponding to the recursion – each vertex is labelled by the current value of$n$, has three children, one of which is a leaf. We ... • 278k 5 votes Accepted ### A better upper bound to a recursive function Solving your recurrence, assuming the base case$T(0) = 1, we get \begin{align*} T(n) &= 1 + nT(n-1) \\ &= 1 + n + n(n-1)T(n-2) \\ &= 1 + n + n(n-1) + n(n-1)(n-2)T(n-3) \\ &= \... • 278k 5 votes ### Find an upper bound for T(n)=T(\sqrt{n})+10\log\log n An alternative solution still using domain transformation/change of variables.T(n) = T(\sqrt{n}) + \log \log n$1. Let$m = \log n$We can then define a new function$S$based on how$m\$ ...
• 4,511

Only top scored, non community-wiki answers of a minimum length are eligible