Linked Questions
11 questions linked to/from Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem
2
votes
0
answers
495
views
Why can't we use the Master Theorem on recurrences with floor or ceiling operations? [duplicate]
From my understanding, using such operators on large numbers doesn't have an impact on running time, since the integer rounding becomes negligible after a certain point. For example, the recurrence $$...
- 21
3
votes
0
answers
36
views
Power of 2 assumption in Divide and conquer [duplicate]
Currently doing an Algorithms course in my 2nd year of university (I am a maths student, but thankfully at Warwick University, we have quite a flexible degree). One of the topics we cover is the ...
- 31
94
votes
11
answers
28k
views
Solving or approximating recurrence relations for sequences of numbers
In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...
- 72.1k
18
votes
5
answers
6k
views
21
votes
2
answers
6k
views
How to describe algorithms, prove and analyse them?
Before reading The Art of Computer Programming (TAOCP), I have not considered these questions deeply. I would use pseudo code to describe algorithms, understand them and estimate the running time only ...
- 621
4
votes
1
answer
908
views
Master Theorem and rounding up to the nearest integer
For the master theorem for recurrences of the form
$$T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)\,,$$
what difference would it make if the split was into calls of $\lceil n/b\rceil$ instead of $n/...
- 43
1
vote
1
answer
1k
views
Show that $T(n) = 2T(\lfloor n/2\rfloor) + n$ is $\Omega(n\log n)$ using substitution
I have to solve this using the substitution method.
Floor functions cannot be skipped.
IH: Assume that $T(k) \geq ck\log(k) $ for all $k \leq n$, where c is a constant.
IS: Must prove $T(k) \geq ...
-1
votes
1
answer
990
views
Satisfying all the conditions of case 3 of the Master Method except the regularity condition
The regularity condition of case 3 of Master Method says that $af(n/b) < cf(n)$, for $c < 1$.
How to devise a recurrence relation that satisfies all other conditions of case 3 except the ...
- 149
2
votes
2
answers
848
views
How to apply the substitution method to n/2?
I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it.
In standard induction proofs you prove a base case, assume it holds for n ...
Shawn
1
vote
0
answers
882
views
Why do we count the ceils and floors in recursive functions?
When we solve the recursive functions using substitution method, the impact of ceil and floor functions is trivial when the size of the input is large enough. For example the answer of
$$
T(n) = T(\...
- 1,519
4
votes
1
answer
94
views
Is it enough to show the number of steps for certain values of $n$ in order to state an algorithm's complexity?
If I can easily state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, the number of steps is $n\log n$, is this enough to allow me to ...
- 225