Need time complexity of this algorithm

ALGO_Set_Cover (U [1…..n])
//This algorithm gives the minimum set cover of a set S= {S1, S2….} where S1,S2,…are //subsets of S and their union gives the universal set U.
// Input is an array U[1….n] consisting of elements in universal set U.
// Output is a set T = { T1T2…..Tk } such that T is the minimum cover of S.

R<-U
T <- {Null}
While(R ≠ Empty )
Choose a subset Si belongs to S where 1≤i≤ k such that maximizes |SiR|
R <- R-S
T <- T U {Si }
Return T
 
Code:
R<-U 
      T <- {Null}
While(R ≠ Empty )  [B]O(min(|U|, |S|))[/B]
{
    Choose a subset Si belongs to S where 1≤i≤ k such that maximizes |SiR| [B]O(|S||U|)[/B]
    		R <- R-S 
    		T <- T U {Si } 
}
       Return T

Total complexity-> O( |U||S|min(|U|,|S|) )
 
Top Bottom