Time Complexity of a Union Find algorithm

Question

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.

Answer 1

Figured this out. Since uf.Union is an inverse ackermann it grows so slowly that it could be considered constant. thus the second loop would run O(clgn) giving and expected output of O(n + clg n))