# How to prove a recursive's function Big-Theta without using repeated substitution, master theorem, or having the closed form?

I have a function defined: $$V(j, k)$$ where $$j, k \in \mathbb{N}$$ and $$t > 0 \in \mathbb{N}$$ and $$1 \leq q \leq j - 1$$. Note $$\mathbb{N}$$ includes $$0$$.

$$V(j, k) = \begin{cases} tj & k \leq 2 \\ tk & j \leq 2 \\ tjk + V(q, k/2) + V(j - q, k/2) & j, k > 2\end{cases}$$

I am not allowed to use repeated substitution and supposed to prove it by induction. I can't seem to use the master theorem because the recursive part is not in that form. Any ideas on how I can solve it with the given restrictions?

If I start with induction: I fix $$j, q$$ and induct on $$k$$. Then the base case is $$k = 0$$. Then $$V(j, 0) = tj$$. The question hinted that the function can be $$\Theta(jk)$$ or maybe $$\Theta(j^2k^2)$$ (but it doesn't necessarily have to be one of the two).

I choose $$\Theta(j, k)$$. In the base case, this would mean I would have to prove that $$tj = \Theta(j, k)$$ when $$j = 0$$. However, when I start with the Big-Oh, I would have to show that $$km \leq mn = m\cdot0 = 0$$ which right now I see not to be possible.

I am not sure if I did the base case wrong or if there is another approach to this.

• @CurtisF I am not sure about when $k$ is not a power of 2, but sometimes we assumed for some proofs which would need that assumption. So it's possible you can assume that. Nov 9, 2019 at 3:25
• Possible duplicate of Solving or approximating recurrence relations for sequences of numbers Nov 9, 2019 at 7:37
• @DavidRicherby I don't think so. Nov 9, 2019 at 8:13