> &(%Y bjbjWW 9==nb]:::::::NNNN8$,N|~~~~~~$:"u ::u u u ::|NN::::|u u gh::|pK
NNlEECE 352
Problem Set #2
Due: September 8, 1998
Fall 1998
Problem 1 (25%): Indicate for each pair of expressions (A,B) in the table below, whether A is O, (, or ( of B. Assume that k ( 1, d > 0, m > 0, and b > 1 are constants. Your answer should fill each one of the boxes with either a yes or a no. Show your work, that is, prove that each answer is correct.
ABO((lgknnkYesNoNonk(nYesNoNo EMBED Equation.3 nsin nNoNoNo2n2n/2NoYesNonlg mmlg nYesYesYes
a. lgkn = O(nk)
(lg n)k ( c nk
(lg n / n)k ( c which is true since k(1 and the fraction goes to 0 by LHopitals rule.
b. nk = O((n)
nk ( c (n
nk/(n ( c is true by LHopitals rule. We can take the derivative of the numerator until it becomes a constant, while we can take the derivative of the denominator an infinite number of times and will stay the same (good old (n---it stays the same no matter how many times you integrate it or differentiate it).
c. We cannot prove any of them because the sin n prevents the function from converging to any value. It is never true that, for all n > n0, A will be bigger than B or B will be bigger than A.
Following is the plot of nsin n. As you can see, the function never settles down to a small or a big value.
d. 2n = ((2.5n)
2n ( c2.5 n
c ((2/2.5)n
c ( 1.44n is true for c = 1 because this number goes to infinity as n goes to infinity.
e. If we take the logm of nlg m and simplify, we end up with A = (lg m)(logmn). If we do the same for B we end up with B = (logm n)/(logm 2). Notice that they are both a function of logmn times some constant. Therefore, they are both really the same function multiplied by a constant. In big-O notation, if two functions are the same except for a constant factor then they are considered to be the same.
Problem 2 (25%): Rank the following functions in order of growth. That is, find an arrangement g1, g2, , g10, satisfying g1 = O(g2), g2 = O(g3),and so on. Partition your list into equivalence classes such that f(n) and g(n) are in the same class if and only if f(n)=((g(n))..
n2n!lg2n2nlg nlg lg n(lg n)lg n(lg n)!n lg n2lg nn1
Remember that n! = 1(2(3(((n (it is called n factorial).
Show your work. The solution to this problem starts like:
1 < lg lg n < lg n < lg2 n < (n = 2lg n ) < n lg n < n2 < (lg n)lg n < (lg n)! < 2n < n!
Problem 3 (25%): Exercise 2.6 from the Weiss book.
A.1. O(n) 2. O(n2) 3. O(n3) 4. O(n2) 5. O(n5) 6. O(n4)
Problem 4 (25%): Exercise 2.7 from the Weiss book.
1. The probability that A[0] contains some number x is simply the probability that rand_int(0,n) returns x. This is, by definition, 1/n for all numbers x between 1and n. Given that A[0] contains any number x with equal probability then, A[1] will also contain any number x with equal probability. By induction, we can say that A[i] will contain any number x with equal probability.
2. The proof is the same as the previous one.
3. Proof by induction: For the case where n=2 we can see that the loop only executes once and, when it does, it executes either Swap(A[1],A[0]) or Swap(A[1],A[1]), each with equal probability. This means that, for this case, the two possible ordering of {1,2} and {2,1} are equally likely.
For the n+1 case we start with the assumption that the array from A[0] to A[n-1] contains an even distribution of the integers between 0 and n. The value of i is now n and we are executing the statement Swap(A[n], A[Rand_int(0,n)]). We also have that A[n] = n +1. Looking carefully at the Swap statement we notice that the probability that A[n] will contain any number between 1 and n is equal to 1/n. That is, A[n] will be swapped with itself with probability 1/n, and with any other integer also with probability 1/n.
B. 1. O(n3) 2. O(n2) 3. O(n)
Handing it in: You will hand in a hardcopy with your name and all your answers. As always, the deadline is at 4:00pm, no exceptions.
Department of Electrical and Computer Engineering
University of South Carolina
- PAGE 2 -
9:J0>mstuvz{~#$%&?@svwx}ƽݷ
jCJjCJEHUj9
UVmH
jCJU
jeCJCJH*5
jCJ6CJ
jQCJ
jWCJ5CJCJH /9:lmoqsuwx}LD$$l
t~ xr$$ $$$$ /9:lmoqsuwx}¾zupkgb]X
b
g
jk
n
q
t
{
"rsڤLd$$l
t~ xr$$rs , !78;>CFGLT_g¿~zupkf
$46cd-=>?
C
G
K
Q
WX
[
_(}~DEstuQRUX ! " & ( ) * 2 3 9 :
E
F
!1uv
jCJ
jWCJ jUCJH*:CJCJNH5CJ
jCJCJCJH*
jeCJPs , !78;>CFGLT_ghH$$l:,"$(-.49:@ACDFZ_pu
(
)
2
6
D
E
N
^
5CJ
jCJH*CJH*
jQ6CJCJH*CJ
6CJH*6CJUghouwyz{M
N
mlmno¿
$)1T@ Atu>?yz
$houwyz{M
N
mlh
&F$$l:,"$
mo nhmHjUhnH hnH CJH*CJ5CJ5lmno$$&d / =!"#$%n Xy
pJPNG
IHDRngAMA cIDATxvQsV9n81/fL"?XqyD;4 Fh\
Kri4@.ȥ4 Fh\
Kri4@.ȥ4 Fh\
Kri4@.iq`4 WPiz^vI5zy_ܽ/
@Ari4@.ȥ4 WP(5hdO
@Ari4@.ȥ4hYrF[
PjFȥ4 Fh}h
A>hstjrbokRiyl9}7DZkΟG?ק>8ֱ-઼g;^(Zǖ-@RӶC̣gwՋݱY\_$F{|Zu>@TvI
A٤Wh
ٺFh\
K\۽F[
i!~h
AbFhi_4 FC;̑ǣ|jF[
Pj4ȥ4yü7{6
Kr5hBPff!85ت;=&
qŖ-1֜i!y˖w$T2ay4zJF#J?^m|1FzÇo-[OMEѻ@ĎO\
%hen44aAѴ6">?$p$@c<է4 F\hF3:ѻF
jܠ8r~pG8#HP8*p2ȥ4 Fӣ.2Z#45h,fTA>h$sW=4 FhRyEM15;BP(5x<\erAS(tS烈.Ku[(j4MF4Sԧ4zSnayz[̽#AN_{W{2G
*m {^o
F_a0M$e4 Fs/G`^yY-)k=xݓW jџ8+"
@aF0og|: ;pX>BX;xwM4:<3@H)^Lӎ]͵o|<'ywdmsPo]X~rO-z99]9095{/lg_[6v#ܕ#s<5'͝kWG_g+GhzѺ_]AOҋ{у#Z_u0baCrJpM.i4x:Zl+Mg̣U%G2iz!@.h\
Kri4@.ȥ4 Fh\
AGIENDB`Dd|hB
SA?2yCa;[ gE;UD`!MCa;[ gE;`@0|xcdd``~ @c112BYL%bL0Yn&&! KA?H
@߀jx|K2B*R8 :b`e-f 30V*e
x͜k'rAj1$&
L
&O@Hfnj_jBP~nbV1s-c`vF;<ķ\a
CCF&&\`] sِ;]`<
!"#$'*+8,./01234567Root EntrydocA8ܽ
FXOӽ`ʐ
)Data
WordDocument 9ObjectPool(
`ʐ
_965736386FT*
.
Ole
CompObjfObjInfo
FMicrosoft Equation 3.0DS EquationEquation.39q |
nOh+'0t
$0<
HT\dlEquation Native 21Table-ASummaryInformation(DocumentSummaryInformation8 EECE 352 ECE jmvidal0 mvi352psl0 jmvidal0 2viMicrosoft Word 8.0@@؟#ܽ@w
@w
;՜.+,D՜.+,Thp
!University of South Carolina-ECE2j EECE 352Title 6>
_PID_GUIDAN{E11F42A7-3533-11D2-B2B1-0040052DB186}
FMicrosoft Word Document
MSWordDocWord.Document.89q
[$@$NormalmH HH Heading 1$<@&5CJKHOJQJ4@4 Heading 2$@&5CJ(0@0 Heading 3$@&CJ 4@4 Heading 4$$@&CJ88 Heading 5$$@&5CJ$4@4 Heading 6$@&5CJ00 Heading 7$@&CJ4@4 Heading 8$$@&CJ$8 @8 Heading 9 $$@&5CJ<A@<Default Paragraph Font,,Header
!, @,Footer
!8Y8Document Map-D OJQJ(U@!( Hyperlink>*B*0aaad}
shl
g:SZ\d!/Xb$}>z_b$Xy
pJ 0@t(
<
#AB
S ?/j4x|} `jvxBGGILNOQUWZ\`bjl " - / 2 4 : < B
J
89[
\
nsu0> vx 01;<`b
68
njmvidal05\\engr_asu\Z_jmvidal0$\EECE 352\Handouts\PS2-sols.docjmvidal05\\engr_asu\Z_jmvidal0$\EECE 352\Handouts\PS2-sols.docjmvidal05\\engr_asu\Z_jmvidal0$\EECE 352\Handouts\PS2-sols.docjmvidal05\\engr_asu\Z_jmvidal0$\EECE 352\Handouts\PS2-sols.docjmvidal05\\engr_asu\Z_jmvidal0$\EECE 352\Handouts\PS2-sols.docjmvidal05\\ENGR_ASU\Z_jmvidal0$\EECE 352\Handouts\PS2-sols.docjmvidal05\\ENGR_ASU\Z_jmvidal0$\EECE 352\Handouts\PS2-sols.docjmvidal05\\ENGR_ASU\Z_jmvidal0$\EECE 352\Handouts\PS2-sols.docjmvidal05\\ENGR_ASU\Z_jmvidal0$\EECE 352\Handouts\PS2-sols.docjmvidal05\\ENGR_ASU\Z_jmvidal0$\EECE 352\Handouts\PS2-sols.doc2 X^j!`zƋ,kPGzmhho(.hho(.05o(-hh5o(-88o(.,k !`X2@ p P@GTimes New Roman5Symbol3&Arial5&Tahoma"qhs)&s)&K)f;!20d (C:\win32app\MSOFFICE\Templates\352PS.dotEECE 352jmvidal0jmvidal0CompObjj