I have a algorithm and i want to prove with induction, need help!

Question

Hello, i have a algorithm and i want to prove it with induction how can i do that ?

Also i want to worst case run time analyze but i am not very good please help me please.

Thank you so much!

 

Comments

Here , there is no base case . then how we decide where this algorithm will stop?? if third<1 ?? .. i think queston is iscomplete ..

---

Here the base case is if(min<max)

---

The time complexity is theta(n).

Recurrence relation for time:

T(n) = 3T(n/3) + c where c is constant and T(n) is the time to sort n elements using NancySort.