2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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))

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.