rovim
rovim

Reputation: 68

Time complexity of a recursive function where n size reduces randomly

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

Answers (1)

Sel&#231;uk Cihan
Sel&#231;uk Cihan

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

Related Questions