Proof by induction long question

Question

I've been trying to figure this question out for a while:

An algorithm takes one operation to sort an array with one item in it. When the number of items in the array increases from n to n+1, at most an additional 2n+1 operations are required. Use proof by induction to show that the number of operations required to sort the array with n>0 items in it requires at most n² operations.

I understand proof by induction, and have done several examples pf shorter-style questions however can't think how to extract the required information from this question.

Thanks in advance.

Answer 1

Basis for induction: For n = 1, the result holds.

Induction hypothesis: Suppose $k^2$ operations are required to sort k terms.

Inductive step:For k+1 terms, maximum operations required are the maximum operations required for k terms+ maximum operations required for the next step

=$k^2+(2k+1)$

=$(k+1)^2$

Hence proved

Hope it is helpful