## Exam Information

Login / Sign Up to View Document

## 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

© Copyright 2020 , Koofers, Inc. All rights reserved.

The information provided on this site is protected by U.S. and International copyright law, and other applicable intellectual property laws, including laws covering data access and data compilations. This information is provided exclusively for the personal and academic use of students, instructors and other university personnel. Use of this information for any commercial purpose, or by any commercial entity, is expressly prohibited. This information may not, under any circumstances, be copied, modified, reused, or incorporated into any derivative works or compilations, without the prior written approval of Koofers, Inc.