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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.