Question

Why partition() in quicksort average case is n+1 why?

Answer 1

It is o(n).

For each partition step ( to bring a element on it's right place ) it takes only one loop .

NOTE THAT for each pivot it is o(n) ( only for one step ) . Not for whole algorithm .

We take two varible , one to track the element which is bigger than pivot and other one is loop varible , whenever we get smaller number ( than pivot ) we swap them and do +1 in tracking element .

Read the algorithm , and you will get clear picture of this :)