16 votes

Solving a recurrence relation with √n as parameter

In your comment you mentioned that you tried substitution but got stuck. Here's a derivation that works. The motivation is that we'd like to get rid of the $\sqrt{n}$ multiplier on the right hand side,...
user avatar
  • 14.6k
9 votes

How to solve T(n)=2T(√n)+log n with the master theorem?

Let us actually use the master theorem. Define $S(n) = T(e^n)$ for all $n$. Then $$S(n) = T(e^n) = 2T(\sqrt{e^n}) + \log(e^n) = 2T(e^{n/2}) + n = 2S(n/2) + n$$ Now we can apply the second case of ...
user avatar
  • 34.9k
8 votes
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 ...
user avatar
  • 1,336
7 votes
Accepted

Master Method to solve recurrences is 'a' related to 'b'?

No it's not always the case that $a=b$, since you might not necessarily use every sub-problem. Consider for example, the binary search algorithm. In the algorithm, you have a sorted array that you ...
user avatar
7 votes
Accepted

Intuition behind the Master Theorem

You can use repeated substitution to obtain $$ T(n) = f(n) + af(n/b) + a^2f(n/b^2) + \cdots $$ Now suppose that $f(n) = n^\gamma$. Then $$ \begin{align*} T(n) &= n^\gamma + a (n/b)^\gamma + a^2 (n/...
user avatar
7 votes

How to solve $T(n)= 4T(\sqrt n) +\log^2n$?

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 ...
user avatar
6 votes
Accepted

Master Theorem and rounding up to the nearest integer

Yes, this is generally valid. Normally, you can just replace $\lceil n/b \rceil$ with $n/b$ and carry on. Why is this valid? Let me give three explanations, in order of decreasing amount of hand-...
user avatar
  • 143k
6 votes
Accepted

Using the Master theorem on a recurrence with non-constant a

This is not solvable using (only) the Master Theorem. It's not in the correct form. The Master Theorem only applies when there's a constant in front of the $T(n/b)$, and $3^n$ is definitely not a ...
user avatar
6 votes

Applying the Master Theorem on Merge sort

You can't use $n/2$ since this bound just isn't always true. Suppose that $n = 5$. It is not the case that you can split an array of length 5 into two arrays of length 2.5. It's not even true that you ...
user avatar
6 votes
Accepted

Master theorem for $T(n)=T(n-1)+O(n)$

The master theorem isn't the appropriate theorem for every recurrence. As an example, your recurrence isn't of the type tackled by the master theorem, though it is easy to solve directly using the ...
user avatar
6 votes
Accepted

Merge sort: sorting and merging complexity $\Theta(n)$

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 ...
user avatar
  • 87
5 votes
Accepted

What kind of recurrence relations has p < 0?

As Rick Decker mentions, in this context $\log^p n = (\log n)^p$, and so $p$ can be an arbitrary real number. If you wanted to denote composition, you would use $\log^{(p)} n$ (which in other contexts ...
user avatar
5 votes
Accepted

What is the case 2 in master theorem?

There are several different versions of the Master Theorem. This situation is common in mathematics: a well-known theorem may have several common versions, for example the Chernoff–Hoeffding bound(s). ...
user avatar
5 votes
Accepted

Conditions for applying Case 3 of Master theorem

Yes, your sharp observation is completely correct. To be compatible with the highly strict style shown at section 4.6, Proof of the master theorem of Introduction to Algorithms, here is the complete ...
user avatar
  • 34.9k
5 votes
Accepted

Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

You are right: you can apply the Akra-Bazzi method to find that $T(n) \in \Theta(n)$. Your professor is right: since $\Theta(n) \subseteq \mathcal{O}(n\log n)$, it is also true that $T(n) \in \mathcal{...
user avatar
  • 7,203
4 votes
Accepted

How to deal with $n\sqrt n$ in master theorem?

You have to remember that $\sqrt[x]{y} = y^{\frac{1}{x}}$. Then the rest should follow easily. Don't look at the following unless you're genuinely stuck.
user avatar
4 votes

How do we derive the runtime cost of Karatsuba's algorithm?

Thank @Josiah for the question and Wiki explanation! To clearly see the runtime of Karatsuba's algorithm for the multiplication of two complex numbers by recursion with Gauss's trick, I would like to ...
user avatar
  • 41
4 votes

Meaning of the constants that appear in the Master Theorem

That is not the general formula for time complexity. There is no "general formula for time complexity", any more than there is a "general formula for the answer." Rather, the formula you give is a ...
user avatar
4 votes
Accepted

Run time of a Simple Recurrence

First let's see how we arrive at the solution. Let's try expanding it: $$\begin{align} T(n) & = T(n^{\frac{1}{2}}) + \Theta(\lg \lg n)\\ & = T(n^{\frac{1}{4}}) + \Theta(\lg \lg n^{\frac{1}{2}})...
user avatar
  • 4,371
4 votes

What is the recurrence form of Bubble-Sort

Bubble sort uses the so-called "decrease-by-one" technique, a kind of divide-and-conquer. Its recurrence can be written as $$T(n) = T(n-1) + (n-1).$$
user avatar
  • 9,219
4 votes

How to solve T(n)=2T(√n)+log n with the master theorem?

As discussed in the other answer, the Master Theorem does not apply here. To solve this recurrence, we can follow the similar steps in Solving recurrence relation with square root. For $n=2^m$, we ...
user avatar
  • 1,016
4 votes

How to use Master Theorem with strange format of $b$ parameter?

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(...
user avatar
4 votes
Accepted

Could I apply the master theorem if my $N/b$ is $\varphi(N)$?

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)) &...
user avatar
  • 2,209
4 votes
Accepted

Justifying a claim in the proof of the master theorem

Suppose that $f(n) = O(n^{\log_b a - \epsilon})$. According to the definition, there exist constants $N,C>0$ such that $f(n) \leq Cn^{\log_b a - \epsilon}$ for all $n \geq N$. Let $M$ be the ...
user avatar
4 votes
Accepted

How can we get upper bound in terms of Big Oh notation using Master theorem?

Your reasoning is wrong. It is in $\Theta(n^{\log_2(5)})$. Hence, it is also in $O(n^{\log_2(5)})$. Answer to the update: Also, for the update part, it is wrong. You can find it by a straightforward ...
user avatar
  • 3,512
3 votes
Accepted

Applying Master Theorem to: T(n) = T(n - 2) + n^2

Think about what the derivative of T is. If the difference between T (n) and T (n-2) is $n^2$ then the derivative T' (n) is about $n^2 / 2$ and T (n) is about $2/3 · n^3$.
user avatar
  • 25.5k
3 votes
Accepted

How do we derive the runtime cost of Karatsuba's algorithm?

"Karatsuba's basic step works for any base B and any m, but the recursive algorithm is most efficient when m is equal to n/2, rounded up." I understood this to mean that for integers with n digits, ...
user avatar
  • 161
3 votes
Accepted

Reccurence of recursive function with unequal sizes of subproblems

Your timing function is $T(n)=2T(n/3)+1$, namely two recursive calls to one-third size problems plus a constant amount of time for the if test and the assignments. If you know the Master Theorem, the ...
user avatar
  • 14.6k
3 votes
Accepted

Can anyone explain why this is an inadmissible recurrence case that cannot be solved by the master theorem?

A non-polynomial difference just means that the quotient $\frac{n/\log n}{n^{\log_b a}} = \frac{1}{\log n}$ is not a polynomial, where here $a=b=2$. To see why this is a problem, let's try to apply ...
user avatar
3 votes
Accepted

Satisfying all the conditions of case 3 of the Master Method except the regularity condition

For a run-time recurrence to satisfy all conditions of case 3 and not satisfy the regularity condition, we have to think of such $f(n)$ that grows or shrinks by a factor of $a$ when $n$ is decreased ...
user avatar
  • 139

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