find1()

Θ(1)

merge1()

Θ(N)



n find1()

Θ(n)

m merge1()

Θ(mN)=Θ(n^{2})

Total

Θ(n^{2})


find2()

Θ(N)

merge2()

Θ(1)



n find2()

Θ(n^{2})

m merge2()

Θ(m)=Θ(n)

Total

Θ(n^{2})


find2()

Θ(log N)

merge3()

Θ(1)

merge3() 
keeps height ≤ log N 

n find2()

Θ(n log n)

m merge3()

Θ(m)=Θ(n)

Total

Θ(n log n)


find3()

Θ(log N)

merge3()

Θ(1)

find3() 
performs path compression 

n find3()


m merge3()

c = n + m

Total

Θ(c α(c,N)) = Θ(c) = Θ(n+m) = Θ(n)

