-1
votes
0answers
29 views

How To Solve the recursion?

Need help with the following recursion: $$T(n)=2T\left(\frac n2\right)+ \frac n{\log n} $$ I Tried to solve it to no avail, and the master theorem doesn't seem to work on it. Thanks
0
votes
0answers
45 views

How can I find the distribution of a recursive relation with two parameters?

Suppose we have a recursive relation, e.g. $G(n,m) = G(n-1,m) + G(n, m-1)$, with some initial points where $n,m \in \mathbb{Z}^{+}$ and $F$ is a finite-field, e.g. $\mathbb{Z}_p$ for a prime $p$. Also ...
0
votes
1answer
64 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
1
vote
1answer
45 views

Course-by-values recursion

I have many questions in my textbook of the kind: Assume $g$ is primitive recursive and assume $f(0)=c_0,\dots,f(n-1)=c_{n-1}$ $f(x+n)=g(<f(x),\dots,f(x+n-1)>)$ Prove that $f$ is primitive ...
0
votes
0answers
45 views

Proving a function is primitive recursive

Assume $f$, $r$, and $s$ are primitive recursive. Prove that $$h(\overline x,y) = \begin{cases} f(\overline x,y,h(\overline x,r(y))) & r(y)<y \\ s(\overline x,y) & \text{otherwise} ...
0
votes
1answer
112 views

“Nested” recursion preserves primitive recursive functions

Problem: Assume the functions $f$, $\pi$, and $g$ are given. They take one, two, and three arguments respectively. Prove a unique function $h$ exists such that: $$h(0,y)\cong f(y)$$ $$h(x+1,y)\cong ...
3
votes
1answer
149 views

Issue while applying Master Theorem

I've read about the master theorem for solving recurrences in Introduction to Algorithms, but have a problem (probably, due to misunderstanding) while applying it in some cases. For example, having ...
2
votes
2answers
200 views

solving a non-standard recurrence relation in asymptotic terms (using Big O notation)

Looking at the following recurrence relation: $$ T(n)= T(n-x)+T(x)+O(\min(x,n-x)) $$ $$ T(1)=1 $$ where $x$ can devide our problem in any proportion (may vary from call to call -- not a constant ...