New answers tagged

0

You would just need to follow Akra-Bazzi's argument for your particular case. Let's prove that $$T(n)\in\Theta\left(n^2\left(\frac{3}{2}-\frac{1}{2n^2}\right)\right)$$ Here $$\frac{3}{2}-\frac{1}{2n^2}=1+\int_{1}^{n}\frac{dx}{x^{2+1}}$$ First let $b=\min(3,\frac{3}{2})=\frac{3}{2}$. Let $k_n$ be the smallest positive integer such that $n/b^{k_n}<1$. Call ...


1

More interesting than solving the recurrence is to show where exactly your complete induction proof went wrong. To show a statement S(n) by complete induction you prove manually that S(n) is true for all $n ≤ n_0$ for some $n_0$, and then you show that for $n > n_0$, if S(n') is true for all n' < n, then S(n) is also true. That's a quite general form ...


1

Ok lets try solving this by substitution , $T(n) = 2T(n-1) + 1$ from this we know , $T(n-1) = 2T(n-2) + 1$ so $T(n) = 2(2T(n-2) + 1) + 1$ $T(n) = 2^2T(n-2) + 3$ lets substitute one more time $T(n-2) = 2^2T(n-3) + 1$ $T(n) = 2^2(2T(n-3)+1) + 3$ $T(n) = 2^3 T(n-3) + 7$ Hopefully you can notice the pattern now $T(n) = 2^{k}T(n-k) + 2^{k}-1$ So , for $k = n$ $T(...


1

For sure, $T(\sqrt{n})\leq T(n)$, so $T(n)\leq 2T(n-1)+n$, but this produces an exponential upper bound, which is correct but to big to be useful. Anyway, in this case if we start from the solution of the recurrence $S(n)=S(n-1)+O(n)$, which is $O(n^2)$, we observe that $S(\sqrt{n})=O(n)$, so also the solution of $T(n)=T(\sqrt{n})+T(n-1)+O(n)$ is in $O(n^2)$....


1

First, let's review the master theorem: The following theorem can be used to determine the running time of divide and conquer algorithms. For a given program (algorithm), first we try to find the recurrence relation for the problem. If the recurrence is of the below form then we can directly given the answer without fully solving it. If the recurrence is of ...


2

Let us assume that $n$ is of the form $2^{2^k}$, and furthermore, a base case of $T(2) = 1$. Applying the substitution method, \begin{align} T(2^{2^k}) &= 1 + 2^{2^{k-1}} T(2^{2^{k-1}}) \\ &= 1 + 2^{2^{k-1}} + 2^{2^{k-1}+2^{k-2}} T(2^{2^{k-2}}) \\ &= 1 + 2^{2^{k-1}} + 2^{2^{k-1}+2^{k-2}} + 2^{2^{k-1}+2^{k-2}+2^{k-3}} T(2^{2^{k-3}}) \\ &= \...


0

Here is a recursive definition of a height of a tree $T$: If $T$ is a leaf, then its height is 0 (some people prefer to use 1). Otherwise, the height of $T$ is the maximum height of any of its children, plus 1. Equivalently, the height of a tree is the maximum length of a root-to-leaf path (in edges; if you measure it in vertices, leaves should have height ...


1

Define a sequence by $n_0 = n$, $n_{i+1} = n_i - \sqrt{n_i}$. Let $\ell$ be the maximal index such that $n_\ell \geq n/2$. For $i \leq \ell$ we have $\sqrt{n_i} \geq \sqrt{n/2}$, and so $n/2 \leq n_\ell \leq n - \ell \sqrt{n/2}$. It follows that $\ell \leq \sqrt{n/2}$. Let $\ell_t$ be the maximal index such that $n_{\ell_t} \geq n/2^t$; so $\ell_0 = 0$ and $\...


1

The solution depends on the initial conditions. For example, if $T(0) = T(1) = T(2) = 2$ then $T(n) = 2$ for all $n$, but in general the recurrence converges to a pattern of length $4$. The limiting patterns are of the form $$ a, \frac{ab\pm\sqrt{(ab)^2-4(a+b)}}{2}, b, \frac{ab\mp\sqrt{(ab)^2-4(a+b)}}{2} $$ For example, if $T(0)=T(1)=T(2)=1$ then $a ≈ 3....


2

Backward substitution is a specific method to solve a particular problem: a linear system of equations; Backtracking is a general paradigm to design algorithms to solve constraint problems in which there can be some sense of "partial solution" and in which the potential invalidity of a partial solution can be tested without completing the partial ...


Top 50 recent answers are included