Exam (elaborations)
CMSC 132 EXAM REVIEW ASSESSMENT TEST WITH COMPLETE SOLUTIONS.
- Course
- Institution
CMSC 132 EXAM REVIEW ASSESSMENT TEST WITH COMPLETE SOLUTIONS.
[Show more]
Content preview
CMSC 132 EXAM REVIEWASSESSMENT TEST WITH COMPLETE
SOLUTIONS
Analyzing vruntime v
Insert velement vinto vposition v0 vof van varray vof vsize vn v(in vjava) v- v vcorrect
vanswer-Runs vin vlinear vtime, v(if vthe varray vis vsize vn vand vyou vdouble vit, vtime vwill
vbe vdoubles vas vwell, vthis vis va vgood vway vto vthink vabout vlinear vtime).
Analyzing vruntime v
Retrieving van velement vfrom van varray vof vsize vn v(at va vparticular vindex, vin vjava).
v- v vcorrect vanswer-When vthe vCPU vhas vto vdo vthe varithmetic vto vget vthe velement
vfrom vthe vspecified vindex, vit's va vconstant vtime voperation. vThe varithmetic vbarley
vtakes vany vtime vregardless vof vwhat vindex vit vis vasking vfor.
(note: vthe vsize vof varrays vin vjava vare vbounded vto v2^32)
Analyzing vruntime v
Program vthat vprints vall vof vthe vn-digit vnumbers v- v vcorrect vanswer-It vis van
vexponential vfunction vmultiplied vby va vlinear vfunction.
Think vabout v2 vparabolas vwhere vone vis vshallow vand vthe vother vis vsteep.
Can vwe vmake vthe vshallow vone vworse vthan vthe vsteep vone vby vmultiplying vit vby
va vlarge vconstant? v- v vcorrect vanswer-- vYes, vall vparabolas vare vin vthe vsame
v"ballpark."
- vIt vdoesn't vmatter vif vone vparabola vstarts vbetter vby vthe vother, vif vyou vmultiply vit
vby va vbig venough vnumber, vit vis vthe vsame vthing.
,Imagine va vparabola vand va vshallow vline vwhere vthe vline vis vclearly vfaster, vwhat vif
vwe vstart vmultiplying vit? vwill vthe vline vstill vbe vbetter? v- v vcorrect vanswer--
vMultiplying vdoes vslow vit vdown vbut veven vwhen vwe vmultiply vby va vlarge vnumber,
vafter vthe vcrossover vwe vstill vsee vthat vthe vred vline vis vfaster. v
- vAs vn vgoes vto vinfinity, vthere vis vno vway vu vcan vmultiply vthe vline vby va vnumber
vand vmake vit vworse.
- vConclusion: vlines vare vbetter/faster vthan vparabolas.
f(n) vas vO(g(n)) vmeans: v- v vcorrect vanswer-As vn vgoes vtoward vinfinity, vf vis veither
vbetter, v(faster/smaller) vthan vg, vor v"in vthe vsame vballpark."
What vdoes v"In vthe vsame vballpark" vmean? v- v vcorrect vanswer-- vEven vthough vg
vmight vseem vbetter v(smaller), vwe vcan vmultiply vit vby va vbig vnumber vand vmake vit
vworse v(bigger) vthan vf(for vbig vvalues vof vn). v
- vWe vcan vfind va vbig venough vvalue vm, vso vthat vf(n) v< vmg(n) vfor vsufficiently vlarge
vn.
On va vtest vFawzi vmay vask: vshow v3n^2 v+ v15n v+ v20 vis vO(n^2)
How vwould vyou vshow vthat? v- v vcorrect vanswer-- vDetermine vwhat vnumber vto
vmultiply vby vn^2 vto vshow vthat vit vcan vbe vworse vthan vthe vfirst vfunction.
- vanswer: v"I vchoose vthe vmultiplier vn v= v4, vnow v3n^2 v+ v15n v+ v20 v< vm(n^2) vas
vlong vas vn v> v20.
Show v100n v+ v150 vis vO(n) v- v vcorrect vanswer-- vKeep vplugging vnumbers vinto vn
vuntil vyou vcould vprove vthe vanswer vis vtrue.
- vI vchoose vm v= v101
- vNow v100n v+ v150 v< vm(n) vas vlong vas vn v> v1000
What vis vthe vbig vO vof vthe vbinary vsearch valgorithm? v- v vcorrect vanswer-O(log vn)
If vf vis vlinear vand vg vis vquadratic, v- v vcorrect vanswer-then vf vis vO(g) vbut vg vis vNOT
vO(f)
If vf vis vlinear vand vg vis vlogarithmic, v- v vcorrect vanswer-then vf vis vNOT vO(g) vbut vg
vIS vO(f)
if vf(n) v= v2^n vand vg(n) v= v3^n, v- v vcorrect vanswer-then vf vis vO(g) vbut vg vis vnot
vO(f)
f vis vO(g) vmeaning v- v vcorrect vanswer-- vf vis veither vbetter v(smaller) vthan vg vor vat
vleast vnot vdramatically vworse.
- vthis vis vbig vO vnotation
f vis vo(g) vmeaning v- v vcorrect vanswer-f vis vdramatically vbetter v(smaller) vthan vg.
Suppose vwe vhave vtwo vfunctions, vf(n) vand vg(n), vand vwe vwant vto vknow: vAre
vthey v"in vthe vsame vballpark"? vif vnot, vwhich vone vis vbetter/worse?
evaluate vthis vlimit:
, vlim v(f(n)/g(n))
n v--> vinfinity
What vdoes vit vmean vif vthis vlimit vcomes vout vas v0? v- v vcorrect vanswer-If vthis vlimit
vcomes vout vas vzero vthat vmeans vwhatever vis vin vthe vdenominator vis vgetting
vbigger vdramatically vfaster vthan vwhatever vis von vtop, vso vf vis vfaster. vWe vcan
vwrite vthis vin vlittle vo vnotation:
f(n) vis vo(g(n))
Suppose vwe vhave vtwo vfunctions, vf(n) vand vg(n), vand vwe vwant vto vknow: vAre
vthey v"in vthe vsame vballpark"? vif vnot, vwhich vone vis vbetter/worse?
evaluate vthis vlimit:
vlim v(f(n)/g(n))
n v--> vinfinity
What vdoes vit vmean vif vthis vlimit vdiverges? v(goes vto vinfinity) v- v vcorrect vanswer-If
vthe vlimit vdiverges v(goes vto vinfinity) vf vis vgrowing vmuch vfaster vso vin vlittle vo
vnotation vwe vwould vwrite:
g(n) vis vo(f(n))
Suppose vwe vhave vtwo vfunctions, vf(n) vand vg(n), vand vwe vwant vto vknow: vAre
vthey v"in vthe vsame vballpark"? vif vnot, vwhich vone vis vbetter/worse?
evaluate vthis vlimit:
vlim v(f(n)/g(n))
n v--> vinfinity
What vdoes vit vmean vif vthis vlimit vequals va vnon vzero vconstant? v- v vcorrect vanswer-
f(n) vis vtheta(g(n))
(check vlecture v40 vfor vtheta vnotation)
Analyzing vcode vfragments
for v(int vi= v0; vi< vn; vi++) v{
System.out.println("Hi");
} v- v vcorrect vanswer-O(n)
Analyzing vcode vfragments
for v(int vi= v0; vi< v100 v* vn; vi++) v{
System.out.println("HI");
} v- v vcorrect vanswer-O(n)
Analyzing vcode vfragments
for v(int vi= v0; vi< vn; vi++) v{
vfor v(int vj v= v0; vj v< vn; vj++) v{
vSystem.out.println("HI");
v}
v} v- v vcorrect vanswer-O(n^2)
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller HIGRADES. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $12.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
79223 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now
