Reputation: 68
I created the following pseudocode but I am not sure how to calculate it's complexity:
(Pseudocode)
MyFunction(Q, L)
if (Q = empty) return
M = empty queue
NM = empty queue
M.Enqueue(Q.Dequeue)
while (Q is not empty)
pt = Q.Dequeue()
if (pt.y > M.peek().y) M.Enqueue(pt)
else NM.Enqueue(pt)
L.add(M)
if (NM is not empty) MyFunction(NM, L)
return L;
MyFunction receives a set Q of n points and a list L in which we will save k subsets of Q (1<=k<=n). When we calculate the first subset we go through all the n points of Q and select the ones that belong to the first subset. For the second subset we go through all the n points of Q except those that are already in the first subset and so on.
So, every recursive call the number of points will be reduced by an integer x until the number of points is 0. This integer x can be different from one recursive call to the other (it can be any value between 1 and n (n being the current number of points))
What would be the complexity of my algorithm then?
I was thinking that my recurrence relation would be something like this:
T(0) = 1
T(n) = T(n-x) + an
Is this correct? and if so how can I solve it?
Upvotes: 0
Views: 183
Reputation: 2034
Without any information on the distribution of points in Q, we can not know how they will be dispatched to M or NM queues.
However, it is easy to calculate the worst-case complexity of your algorithm. To calculate this, we assume that at each recursive call, all points in Q
will end up in NM
except the one that is being added to M
before entering the loop. With this assumption, x
becomes 1
in your recurrence relation. And you end up having O(n^2)
.
Upvotes: 0