# Tag Info

4

Let $S(n) = T(2^n)$. Then $$S(n) = T(2^n) = 4T(2^{n/2}) + n^2 = 4S(n/2) + n^2.$$ You can solve this recurrence using the master theorem, and then use $T(n) = S(\log n)$ to obtain a solution for the original recurrence.

4

You can not apply the master theorem directly. However, you can play with your expression a bit to get an upper bound on which you can then apply the master theorem. First, show that $\phi(\phi(n)) < n/2$. This can be done as such: Let $n = \prod_{i=1}^rp_i^{k_i}$ be the prime factorisation of $n$ ($p_i$ prime, $k_i>0$) Suppose $n$ is even. Then $\... 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\... 3 It looks like there is some typo/inconsistency/misunderstanding somewhere in your class, the slides or your post. Hence, I will start from scratch, addressing the problems I can recognize. Definition of polynomial differences. f(n) is polynomially smaller than g(n) if f(n) = O(g(n)/n^\epsilon) for some \epsilon > 0. f(n) is polynomially larger ... 3 Each iteration of merge sort consist of 2 phases: Merge Sorting the first and the second half separately. Merging the two halves. So in your equation phase 1 is represented by 2T(n/2). This means that merge sort is called on the two halves. This is a recursive call, which is why T is used here. Phase 2 is represented by \Theta(n). Merging two lists ... 3 Let's take the slightly more general case where a=b and f(n)=n\;log\;n (in your case, a=b=3). Assume the usual restrictions on a and b hold. Then n^{log_ba}=n. This might lead us to consider case 3 of the Master Theorem since f(n)=\Omega(n). However, the theorem requires that there exist an \epsilon > 0 such that n\;log\;n = \Omega(n^{1+... 2 Here's the relevant part of the proof, quoting verbatim: First, show that \phi(\phi(n)) < n/2. This can be done as such: Let n = \prod_{i=1}^rp_i^{k_i} be the prime factorisation of n (p_i prime, k_i>0) Suppose n is even. Then \phi(n) = n\prod_{i=1}^r(1-\frac{1}{p_i}) \leq n(1-\frac{1}{2}) \leq n/2. Thus \phi(\phi(n)) &... 2 The error is where you claim that kn=n^c where 0<c<1. This is not correct. Even when k<1, it is still the case that kn=\Theta(n); it is not O(n^c) for any c<1. (Check the definition of big-O notation.) 2 In order to make this answer self-contained, I will repeat the first part of my answer to your other similar question. First, show that for N>2, \phi(\phi(N)) < N/2. This can be done as such: Let N = \prod_{i=1}^rp_i^{k_i} be the prime factorisation of N (p_i prime, k_i>0) Suppose N is even. Then \phi(N) = N\prod_{i=1}^r(1-\frac{1}{... 2 First of all, let me correct the recursion for the running time of merge sort:$$ T(n) = \begin{cases} T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + \Theta(n) & \text{if } n > 1, \\ \Theta(1) & \text{if } n = 1. \end{cases} $$The corresponding recursion for depth is:$$ D(n) = \begin{cases} \max(D(\lfloor n/2 \rfloor), D(\lceil n/2 \rceil)) + 1 ... 2 I am wondering if this means that we can write this first case of the theorem as$f \in o(n^{\log_b{a}})$(and following the same logic,$f \in \omega(n^{\log_b{a}})$for the third case), rather than the more convoluted alternative? That is indeed a natural attempt to understand that "convoluted" condition in simple terms. Unfortunately, it is not correct. ... 2 No, that would be incorrect. Perhaps it is the condition$\varepsilon > 0$which is the root of your confusion. It is supposed to mean that$\varepsilon$is a real positive number and constant (with respect to$n$). If we allow$f \in \omega(n^{\log_b a})$, for instance, then for$a = b = 2$we would have$f(n) = n \log n \in \Theta(n)$as a consequence ... 2 In my opinion the problem statement seems poorly posed. It's not clear what is meant by the problem statement. Normally, if we write$a$or$b$the assumption is that they are a constant: they do not depend on$n$. If they are intended to be a function of$n$, then they should be written as$a(n)$or$b(n)$. Since that wasn't done, the only assumption I ... 2 Nicest version of the Akra-Bazzi theorem I've seen is the one in Lehman, Leighton, Meyer "Mathematics for Computer Science", the discussion starts at page 1019. An (older) print version is available. No proof, though. Would need to slough through Leighton's note to verify that the lecture notes/book version is right (it has somewhat different conditions, ... 1 Apply the definition. Does there exists$\epsilon>0$such that$f(n) = O(n^{1-\epsilon})$? If yes, then case 1 applies (just see the text that you included in the question). If no, then case 1 does not apply. For instance, ask yourself: if$\epsilon=0.1$, does$f(n)=O(n^{1-\epsilon})$? i.e., does$\log n=O(n^9)$? You should be able to take it from ... 1 I am afraid that you fell prey to ambiguous notations. To clarify, the subscript$\frac{n-1}2$in the recurrence relation,$T_n = T_\frac{n-1}2 + 1$must mean the integer division of$n-1$by 2 as used in most programming languages, i.e.,$\frac 22=1$and$\frac32=1$. The following equality does NOT hold, $$\log_2(\frac{n+1}{2}) = \log_2(n+1) - 1,$$ where ... 1 Suppose that your function is always in the range$cN^k$to$CN^k$. Consider the three recurrences $$s(N) = as(N/b) + cN^k, S(N) = aS(N/b) + CN^k, R(N) = aR(N/b) + N^k.$$ For appropriate initial conditions,$s(N) \leq T(N) \leq S(N)$will hold, as a straightforward proof by induction would show. On the other hand, for appropriate initial conditions,$s(N) =...

1

So, we have that $f(n) = O(n^c \log^k(n)) = O(n^0 \log^2(n))$; and since $log_b(a) = log_2(1) = 0 = c$, we are in the 2nd case of the Master's theorem (work to divide the problems is comparable to the work on subproblems (wiki)); thus, applying the theorem, we get $T(n) = \Theta(log^3(n))$. On the floor operation, I don't know what is the cleanest way of ...

1

Here are several ways of solving this recurrence. Throughout, I will assume that $T(0) = 0$. Method 1: Guessing Here are some values of $T(n)$: $$\begin{array}{c|cccccc} n & 0 & 1 & 2 & 3 & 4 & 5 \\\hline T(n) & 0 & 1 & 3 & 7 & 15 & 31 \end{array}$$ If you're familiar with powers of 2, you will recognize ...

1

You can only solve equations using the Master Theorem if they are of form $T(n) = aT(n/b) + f(n)$, where $a \ge 1$ and $b > 1$. Here you can't express your recurrence in above form. And your guess of taking $b = 1$ is completely wrong. The reason for not using the Master Theorem is that you can't express your recurrence in form $T(n) = aT(n/b) + f(n)$ ...

1

What is $\varphi(p)$ when $p$ is prime? Why is this the worst case? Note that the master theorem is not going to be applicable. It handles subdivision into subproblems whose size is a fixed proportion of the original problem's size: $2T(\sqrt N)$ doesn't fit this model.

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 Let me show you how to solve these without using the master theorem. For the first item: $$T(n) = n\log n + \frac{n}{2} \log \frac{n}{2} + \frac{n}{4} \log \frac{n}{4} + \cdots \leq \left(n + \frac{n}{2} + \frac{n}{4} + \cdots\right) \log n \leq 2n\log n.$$ This shows that$T(n) = O(n\log n)$. Since clearly$T(n) = \Omega(n\log n)$, we can conclude that$...

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