I have defined a function: $ 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) + T (j – q, k / 2) & j , k> 2 end {cases} $

I am not allowed to use repeated substitution and I want to prove this by induction. I can not use the main clause because the recursive part is not in that form. Any ideas how I can solve it with given limitations?

When I start induction: I fix $ j, q $ and introduce $ k $, Then the base case $ k = 0 $, Then $ V (j, 0) = tj $, The question indicated that the function may be $ Theta (jk) $ or maybe $ Theta (j ^ 2k ^ 2) $ (but it does not necessarily have to be either).

I choose $ Theta (j, k) $, In the base case, this would mean that I had to prove that $ tj = theta (j, k) $ when $ j = 0 $, But if I start with the big-oh, I have to show it $ km leq mn = m cdot0 = 0 $ which I currently do not think possible.

I am not sure if I did the basic case wrong or if there is another approach.