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.