COMP 352 Lecture Notes - Lecture 10: Empty Set, Xu

• School: Concordia University
• Department: Computer Sci.
• Course: COMP 352
• Professor: T B A

Document Summary

1 call --> 3 call --> 22 calls --> (cid:1007)n-1 calls; therefore o(3n) Input: a set t of n elements a1, a2,an. Output: all the subsets of t stored in a queue q. Create an empty queue q; // constant c1. Create an empty stack s; // constant c1. For (each element ai in t) // executes n times. X = s. pop(); // x holds element in stack. X = x u {ai}; // takes union of of x and set of elements ai. T(n) = c1 + c2((cid:1005) + (cid:1006) + (cid:1008) + 8 + +(cid:1006)n-1) + c3((cid:1006) + (cid:1008) + 8 + + (cid:1006)n-1) Input: set t with n elements a1, a2, an. Return { {} } //the set containing empty set else. Set t1 = t - {an} // take the last element out, which is t1. Set p = recursivesubsetgenerator(t1, n-1) //recursively call method with one less element, which gives powerset of t1.