Linked Questions

2 votes
0 answers
506 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 $$...
hotelfloor's user avatar
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 ...
anon's user avatar
  • 31
97 votes
11 answers
29k 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 ...
Raphael's user avatar
  • 72.5k
18 votes
5 answers
6k views

How long does the Collatz recursion run?

I have the following Python code. ...
9bi7's user avatar
  • 305
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 ...
Yai0Phah's user avatar
  • 621
4 votes
1 answer
950 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/...
Barry S's user avatar
  • 43
1 vote
1 answer
2k 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 ...
JohnMadon1234567890's user avatar
-1 votes
1 answer
1k 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 ...
rrrocky's user avatar
  • 149
2 votes
2 answers
862 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 ...
user avatar
1 vote
0 answers
909 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(\...
M a m a D's user avatar
  • 1,529
4 votes
1 answer
96 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 ...
George Hawkins's user avatar