# Past Exam for CMSC 420 - Data Structures with Nau at Maryland (UMD)

## Exam Information

 Material Type: Mid-Term Professor: Nau Class: CMSC 420 - Data Structures Subject: Computer Science University: University of Maryland Term: -- Keywords: Actual CodeManipulationTransitivityDescriptionReflexivityData Processing  ## Sample Document Text

Answers to Midterm Exam: CMSC 420, Fall 1996 Problem 1. Let F be the set of all functions over the nonnegative integers. Which of the following properties does big-O satisfy? 1a (5 points). Reflexivity: for every f(n) in F,f(n) is in O(f(n)). Page 1 ANSWER: yes. To see this, note that if c=l and n o =l, then f( n) 5{ cf( n) for every n~no. 1b (5 points). Antisymmetry: iff(n) is in O(g(n)) and g(n) is in O(f(n)), thenf(n) = g(n). ANSWER: no. One counterexample is the case where f( n)=n and g( n)=2n. 1e (5 points). Transitivity: iff(n) is in O(g(n)) and g(n) is in O(h(n)), thenf(n) is in O(h(n)). ANSWER: yes. To see this, supposef(n)EO(g(n)) and g(n)EO(h(n)). Then there are numbers cj;;:{), nj;;:{), c 2 ;;:{), n 2 ;;:{) such that f( n)5{cjg( n) for every n~nj and g( n)5{c 2 h( n) for every n~n2. 1fwe let C 3 =CjC 2 and n 2 =max(nj,n 2 ), thenf(n)5{c 2 g(n) for every n~C2. 1d (5 points). Totality: for all f(n), g(n) in F, eitherf(n) is in O(g(n)) or g(n) is in O(f(n)). ...

## Related Documents Actual Code Exam Actual Code Exam