## Exam Information

Login / Sign Up to View Document

## Sample Document Text

Problem 1. Let f(n) and g(n) be any two functions over the set of nonnegative integers.
1a [5]. True or false: either f(n) = O(g(n)) or g(n) = O(f(n)).
ANSWER: false. One counterexample is the case where f(n)=sin(?n) and g(n)=cos(?n).
1b [5]. True or false: if f(n) = ?(g(n)), then there are positive numbers c, d, and n
0
such
that for every n ? n
0
, cg(n) ? f(n) ? dg(n) and cf(n) ? g(n) ? df(n).
ANSWER: true. Explanation: we know there are positive numbers c
1
, d
1
, and n
1
such that for
every n ? n
1
, c
1
g(n) ? f(n) ? d
1
g(n); and positive numbers c
2
, d
2
, and n
2
such that for every n
? n
2
c
2
f(n) ? g(n) ? d
2
f(n). Just let c = min(c
1
,c
2
); d = max(d
1
,d
2
); and n
0
= max(n
1
,n
2
).
Problem 2 [10]. Suppose you are using linked lists to represent an n × n sparse matrix, as
illustrated in Figure 5.5 of the book. In the worst case, how much time will it take to compute
the sum of the elements along the main diag...

## Related Documents

Either...or Exam

Either...or Exam

Particularly Exam

Either...or Notes

Particularly Notes

Traditional Typeface 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.