The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
8 views

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

asked in Algorithms by Boss (41k points) | 8 views

1 Answer

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)$
answered by Active (1k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,814 questions
54,520 answers
188,354 comments
75,319 users