recurrence for insert
insert(A, []) => [A];
insert(A, [B | X]) =>
A < B ? [A, B | X] : [B | insert(A, X)];
T
insert
(0) = 1
T
insert
(N)
<
1 + T
insert
(N-1) ;
Solving:
T
insert
(N)
ë
O(N).