I'm trying to understand the time complexity of an example algorithm. My conclusion was O(n^2) but this was considered wrong. The algorithm is as follows:
input: data: array of sorted n integers
input: n: size of data
input: c:a positive integer between 1 and n-1
delta = Array(n-1)
map=HashMap()
for I =1 to n-1 do:
delta[i] = data[i+1] - data[i]
map.Insert(delta[I],i)
end
heap=MinHeap(delta)
uf = UnionFind(n)
for I =1 to c do:
t=heap.deleteMin()
x=map.Search()
uf.Union(x,x+1)
end
return uf
To my knowledge
the first for loop runs in O(n) time, building the heap takes O(n), and the second for loop would run at O(n^2) times dominating the other complexities.