# Tagged Questions

Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.

43 views

### Proving that this algorithm distributes a quantity as expected

Background (non-essential) Let $Q$ be an integer quantity (of say, marbles) to be distributed into $n$ buckets ($B_1$ ... $B_n$) according to weights. Let $w_1$ ... $w_n$ be the non-negative weights, ...
116 views

### Complexity of subset-generation algorithm

I'm trying to calculate the computational complexity of an algorithm which generates the power set of a set of items. The algorithm works using the recursive formula of the binomial coefficient ...
128 views

### Sum of roots of binary search trees of height $\le H$ with $N$ nodes

Consider all Binary Search Trees of height $\le H$ that can be created using the first $N$ natural numbers. Find the sum of the roots of those Binary Search Trees. For example, for $N$ = 3, $H$ = 3: ...
23 views

### For graphs in a recursive graph class: Does m = O(n) hold?

For recursive k-terminal Graph classes - for example definied in this paper - is it true that |E| = O(|V|)? If so, I would be very grateful for a reference! Thanks!
22 views

### Formula for running-time complexity

I'm regarding a stochastic process $(X_t)$of which the mean starts at $O(n)$ and is reduced by the factor $(1-r)$ in each step with $r = \Omega (1/n^9)$, so $$E(X_{t+1}) \leq E(X_t) (1-r) .$$ Now it ...
30 views

### recursion $t(n)=\sqrt{2} \times \frac{tn}{2} +\log{n}$

I tried substituting $m=\log{n}$ $t(2^n)=\sqrt{2} \times \frac{t2^n}{2}+m t(m)= \sqrt(2) \times \frac{tm}{2}+m$ From here I got $\log {n}$ But with induction I proofed its $\sqrt {n}$
43 views

### Is there an algorithm to generate these specific sequences of numbers?

f(1) = [1] f(2) = [2,1,1] f(3) = [3,2,1,1,2,1,1] f(4) = [4,3,2,1,1,2,1,1,3,2,1,1,2,1,1] ... f(n) = ... The lengths of the lists f(n) are $2^n - 1$ (Mersenne ...
75 views

### Values of the Sudan function

I am talking about the first discovered recursive function which is not primitive recursive. I would like to know the exact values of $\ f(3,3,3), f(2,0,4), f(2,7,1), f(2,3,2)$ (where $f$ is the ...
30 views