1
$\begingroup$

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.

$\endgroup$

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.