4

Not every recurrence falls within the bounds on the master theorem. Your recurrence is an example. However, by unrolling your recurrence, we can come up with an explicit formula: $$ T(n) = 6(n+1) + T(n-1) = 6(n+1) + 6n + T(n-2) = \cdots = \\ 6(n+1) + 6n + \cdots + 6\cdot 2 + T(0) = \\ 6(n+1) + 6n + \cdots + 6\cdot 2 + 6\cdot 1 = \\ 6 \sum_{m=1}^{n+1} m = 6\...


4

What the equation means is that there exist constant $A>0$ and $B,C$ such that $$ |x| \leq A \Longrightarrow Bx^2 \leq e^x-1-x \leq Cx^2. $$ In particular, for small $x$, $e^x$ is very close to $1+x$, since the error is only $O(x^2)$ (when $x$ is small, $x^2$ is much smaller than $x$). The same estimate doesn't hold for large $x$ — indeed, $e^x$ ...


3

Asymptotically, you're right: for big-enough inputs, the $\Theta(n\log n)$ algorithm can be faster. However, this is only true for big enough $n$. It might be that "big enough" means "far bigger than any actual computer can store" or even just "plenty bigger than any input I care about". For a specific example of this, look at matrix multiplication ...


2

I wouldn't overthink it: With $n$ distinct elements you have a $1/n$ chance of a match. On average you will have to look at $n/2$ elements. That's because $\sum_{i=1}^{n/2} 1/n = 1/2$. Worst case of course being that you match on the last thing you look at, so have to look at all $n$ of them.


2

The phrase "the element being searched for is equally likely to be any element in the array" is ambiguous. It might mean two different things: The element is at a uniformly random position in the array. The element is chosen uniformly at random from the set of elements in the array. This ambiguity suggests that the authors are making the hidden assumption ...


2

The definition of $\Theta$ includes two constants that the function is multiplied with, and a smallest n where the relation applies. (There is an $n_0$ such that for all n ≥ $n_0$, $c_1 g(n) ≤ f(n) ≤ c_2 g(n)$). If $n < n_0$ then anything can happen. And if one algorithm comes with much smaller constants, then it may stay faster for some quite large n. ...


1

Your recurrence isn't really defined for $n = 1$. This suggests using a different value for the lower bound in the integral. The formula given by Akra–Bazzi doesn't actually depend on the exact value of the lower bound that you choose – it can at most affect the big Theta constant or, in your case, some lower order term. If you choose any lower bound which ...


1

You cannot use master Theorem (at least not as a black-box) as it only provides an asymptotic bound on the growth of $T(n)$, while you're interested in bounding the multiplicative constant too. You can prove an upper bound your to your recurrence by induction on $n$. The case $n=0$ is trivial as $T(0) = 0 = 8n^2$. For $n \ge 1$ you have (notice that $\...


1

I was thinking of using the Master Theorem to get asymptotically tight bounds of the recurrence but I think that is not a right approach. You are correct. While the master theorem can yield asymptotically tight bounds, the question asks you to prove an exact inequality, $T(n) \leq 8n^2$ for all for $n\in\mathbb{N}_0$. Since this is a proposition on natural ...


1

The transformation: You define $S(m) = T(2^m)$ which is absolutely fine. $T(m) = T(m^{1/2}) + m$, so $T(2^m) = T(2^{m/2}) + 2^m$. Therefore $S(m) = T(2^m) = T(2^{m/2}) + 2^m = S(m/2) + 2^m$. That's the mistake you made, the last term is $2^m$ and not $m$. Try $n = 2^{1024}$: $T(2^{1024}) = T(2^{512}) + 2^{1024} = T(2^{256}) + 2^{512} + 2^{1024}$ and ...


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