Koofers

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:Fall 1996
Keywords:
  • Actual Code
  • Manipulation
  • Transitivity
  • Description
  • Reflexivity
  • Data Processing
Login / Sign Up to View Document
Preview Page 1Preview Page 2

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
155, "/var/app/current/tmp/"