# Tag Info

Accepted

### How long does the Collatz recursion run?

This is Collatz conjecture - still open problem. Conjecture is about proof that this sequence stops for any input, since this is unresolved, we do not know how to solve this runtime recurrence ...
Accepted

### How to solve a recurrence relation with a sum?

Here are several ways to solve your recurrence relation. Guessing Anyone with enough experience in computer science might recognize your recurrence as the one satisfied by $T(n) = 2^n$. Given this ...

### How long does the Collatz recursion run?

You translated the code correctly. There are many methods for solving recurrences. However, it is currently unknown if collatz even halts for all ...

### How long does the Collatz recursion run?

The time complexity function is \begin{cases} T(n)= O(1) \text{ for } n\le 1\\ T(n)=T(n/2) + O(1) \text{ for } n\text{ even}\\ T(n)=T(3n+1) + O(1)\text{ for } n\text{ odd}\\ \end{cases} which can be ...

### Solving or approximating recurrence relations for sequences of numbers

After checking this post again, I'm surprised this isn't on here yet. Domain Transformation / Change of Variables When dealing with recurrences it's sometimes useful to be able to change your ...

### 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 ...
Accepted

### Solving or estimating the recurrence $T(n) = x + T(n-\log_2 n)$

Assuming an appropriate base case, it is easy to see that $T(n) \geq (n/\log_2 n) \cdot x$, since at each step we subtract at most $\log_2 n$, and thus it takes t least $n/\log_2 n$ steps to reach ...
Accepted

### Recurrence relation of the coin change problem

For that recurrence to make sense, $V$ can only be the array that contains the coin values; that is, $V=\{C_1, C_2, ..., C_m\}$. Whenever confronted with a new dynamic programming problem, you should ...
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 ...
Accepted

Accepted

### Solving T(n) = 2T(n/2) + log n with the recurrence tree method

The non-recursive term of the recurrence relation is the work to merge solutions of subproblems. The level $k$ of your (binary) recurrence tree contains $2^k$ subproblems with size $\frac {n}{2^k}$, ...
Accepted

### Time complexity of the fast exponentiation method

Instead of time complexity, it is much simpler here to count multiplications; I'll leave you to figure out the relation between multiplications and time complexity (the exact relation depends on the ...
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-...

### 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 ...

### Algorithms - Solving recurrence-relations/Bounds?

First of all, a recurrence is not necessarily about the running time of anything. So you don't figure out "the running time", you solve the recurrence. Second, your recurrence only possibly makes ...
### Error solving the next recurrence: $T(n)=7T(n/2)+n^2$
Some of your sums have typos, but you already have the right answer. Here's a useful fact about logarithms: $a^{\lg b} = 2^{(\lg a) \cdot (\lg b)} = 2^{(\lg b) \cdot (\lg a)} = b^{\lg a}$ Apply it ...
### The recursion $T(n) = T(n/2)+T(n/3)+n$
If $T(1)\le 6$ and $T(2)\le 12$, we can show that $T(n)\le 6n$ by induction. $$T(n) = T(n/2) + T(n/3) + n \le 6(n/2)+ 6(n/3)+n= 6n.$$ More generally, let $c\gt6$ be a constant such that $T(1)\le c$ ...