Time complexity of Rectangle Covering algorithm

39 views Asked by At

I have a task to submit on greedy algorithms. I wrote this code but I'm not sure what the time complexity of the algorithm is. This problem called "Rectangle Covering".

This is the code:

MinGreedyCutReg(R[])
    cut[] = null
    while R != null
        endIndex = 0
        for i = 0 to R.length-1
            if(endIndex < R[i].r)
                endIndex = R[i].r
        maxCount = 0
        maxIndex = 0
        for i = 0 to endIndex
            updateMax = 0
            for j = 0 to R.length - 1
                if(R[j].l <= i and R[j].r >= i)
                    updateMax++
            if(updateMax > maxCount):
                maxCount = updateMax
                maxIndex = i
        cut.add(maxIndex)
        for i = 0 to R.length - 1
            if(R[i].l <= maxIndex and R[i].r >= maxIndex)
                R.remove(i)
    return cut

I am trying to find the time complexity of the algorithm. I think it is O(n * m) because of the nested loop. My friend tells me it is O(n^2) due to this nested loop. So basically I think the question is what time the nested loops can do and why.

0

There are 0 answers