The Gateway to Computer Science Excellence

0 votes

Give a brief argument that the running time of PARTITION on a subarray of size $n$ is $\Theta(n)$.

0 votes

The for loop will run for $r-p$ times for $A[p....r]$

The other parts of algorithm will be simply $O(1)$ time i.e. constant.

Now since $r-p$ is the size of subarray/array so PARTITION will take time which is at most proportional to the size of subarray/array.

Therefore taking linear time $\Theta (n)$

The other parts of algorithm will be simply $O(1)$ time i.e. constant.

Now since $r-p$ is the size of subarray/array so PARTITION will take time which is at most proportional to the size of subarray/array.

Therefore taking linear time $\Theta (n)$

52,215 questions

60,025 answers

201,249 comments

94,712 users