兩個問題 都是是非題
disjoint-set forest , unique element,wightrule is applied那 下面這個例子會成立嗎？
1.In the worst case, find an element in a set of size n take theta(logn)
在最糟情況find 還是可以保持趨近O(1)嗎？還有disjoint-set 有很多種find和union 那是要用哪一種來看還是，就用最好的find和union呢？
2.The complexity of a comparison based algorithm cannot be faster than O(nlogn)
如果非comparison based algorithm 可以突破nlogn，但是如果是Best case不可以了嗎？ 像這題要考慮Best case嗎@@

1 worst case不是應該用沒collapse的find？ 我覺得第二題題目是 BigO??

第一題 你用最好的find也是O(lgn)，可以翻一下筆記，他會是alpha(n),不會是常數

n大 那是bigO沒錯 手機打字直接用O了XDq大 嗯嗯應該是我錯了會趨近1是在壓縮過的路徑的分攤成本才會這樣

第二題 只要題目沒講 都是指 worst case..

其實是我講錯了… 不過感覺你理解的方向是對的他是考慮用weighting rule 所以union的方式有決定了 這樣worst case才會是lgn

第二題如果用comparison tree看time complexity應該是對的吧，leaf=2^height=n!