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,...
- 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 ...
- 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 ...
- 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 ...
- 1,103
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/...
- 270k
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 ...
- 270k
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-...
D.W.♦
- 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 ...
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 ...
- 270k
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 ...
- 270k
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 ...
- 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 ...
- 270k
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). ...
- 270k
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 ...
- 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{...
- 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.
- 17.7k
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 ...
- 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 ...
- 80.4k
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}})...
- 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).$$
- 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 ...
- 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(...
- 270k
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)) &...
- 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 ...
- 270k
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 ...
- 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$.
- 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, ...
- 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 ...
- 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 ...
- 270k
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 ...
- 139
Only top scored, non community-wiki answers of a minimum length are eligible