0 votes 0 votes Kruskal Time complexity is O(mlog m) then how in upper bound it can be written as - O(m2) ----> How log m = O(m) and O (mn) ---------> How log n = O(n) Algorithms algorithms time-complexity graph-algorithms + – iarnav asked Apr 21, 2018 iarnav 1.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes O(mlogm) is tightest upper bound of kruskal algorithm. abhishekmehta4u answered Apr 21, 2018 • edited Apr 21, 2018 by abhishekmehta4u abhishekmehta4u comment Share Follow See all 3 Comments See all 3 3 Comments reply iarnav commented Apr 21, 2018 reply Follow Share @abhishekmehta4u What if, it would be omega then can we write logm > = c. m and again logm = omega(m) 0 votes 0 votes abhishekmehta4u commented Apr 21, 2018 reply Follow Share no simplly A------>$\Omega (B)$ means B is smaller from A. HERE logm----->$\Omega (m)$ and m is not smaller from logm so it is false . EXAMPLE 1 votes 1 votes iarnav commented Apr 23, 2018 reply Follow Share Thanks a lot, really helpful. 0 votes 0 votes Please log in or register to add a comment.