0 ratings0% found this document useful (0 votes) 14 views14 pagesTime and Memory
time and memory complexity
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content,
claim it here.
Available Formats
Download as PDF or read online on Scribd
Input —> Leode —}—> Output
@® Read
@ Undeystant correct ness,
® Seeate _|——> time Limit
| @ Implement Chhictency Memory Limi t
r Delfi t q
© Giet_ac. -
H -
[ER Test, ble)
{ny caer & r ty
oS’
p> Best cage
AtN
eg? 7 (int i20, ig Nz iitt) {
Cint_j=0; j 0 WN") 3) O(dm) > gm) = ¢ fm) 5 moo) ¥ ym
b) O( fim)
bE) Om) gin) > fn)
(a)
cf(n) ) mal
ot
ge |
C00. 1
ea Tt
—
= :
= Ho i
gs gt) = N2+N
O(N?) as 2N? > NEN (c=2) (n>)
alio
O(ND tN SN ea)
S more tight bound
b)__gin) = © (gem) if G fom <_gin) <_e fm)
ot
ww)
8m)
ee) a fly)
Pe
eS ()__9(n) = 2. (flm))
= gg
a __¢4.(m)
7 =
|
T
1
I
| —————
| Le
|
| eae ain) Nene
| & O(n) a N3_< gin) <_2N#
|
Le =, G = 2)
| Sat)
L *K
___O = upper bound
2 => Lower bound
8 exact loss (xandisich)
ag: gin) = ane + BO
Lowes order term
aaa om
Ss on)
‘ine 0 (Nea) fo13 i <2*n+ ts [tt
! a=
ant
= (2¥ntd) Xk k= J
eee OTe
OM)
(0
Uiz0; ix m4 [4+
Gr04
j4 4p N)f
for jot ion ){] | > om)
O(4) po 4orli> 4 tp wf
for Goi to my kM
tow =>_O0-w)
}
O(N?) + O(N mM)
= O(Niwim) )
H#LConcept 7
+ ol $m) J man bound
| soy Ont) © 2:
| = Tes 4 gee > OUi0*)
© U0)
if
I ON?) < Ip? um can ile
| S_Sx 1p? = safer
| i O(N) > 10” —> X
g* n< lO
then O(nl) or O(n?) will work
n<é 20
then On) or O(n) ns 30 = ov) will wok =
n< 40 > ol”)
”
n_<¢ 4500 — 0 (r*) " ”
I
1A
10° = 6 (NJN)
=
A
5 x08 > O(n log n)
WSS ibe CN)
ns
lo* — O(N) eo OWN og.)
n< to& + O Ugg?) or QU) or Oly N)
mn) = 0" n pete Nt
fhen fin) =_N%
Sine =O (n’) j ie court
21) __imk ans =0; count HEY ant) size y
int i= 0; i iy
while (Ten) ea
[while Gen 44 ali l= v) tay complet ty |
if Gen)f
| angt+ 5 i
i SS np statements ¥ be _exeuted
Attends on i. bach time sone
I
| both loop will byeak af i= N
—Tine_complai ty = O(n) —~
Mempsuy Complex: : —
oxtnitnd SS
co pee) ; Stack : a
oo) ee
aul scope Heap i
| he sake with ax C4)
r Static | Giloha
Text
Se
NP— Hand concept : (mot _sdlyable_in poly” time)
be OW)
Ss 0 (29) or O(N") ete Masten Thepwem :-
n)
if (n=sol|m== ae)
Cow
yen 1 |
| tle
| sutan fibtn- + fipln-2) 1 < hee mater theorem i
at not applicable
Step 4 Note down Ob, ¢ for
ane= atte) ta
b
7
2 Q iG
for_matge sort (nl? | om) = (Gn),otnm)] Spar Ola * 7). ts soe .
; then - }
Time complexity ia Cog, _
ae io In?) YC
then ,
Time _complaity Js 0 (n'*)
Tt _tomplaity 9c
Timne_comn laity = 0 (alogn)
43 : td?
qii_Ton)= 2 T() an’)
sol"s a: 94, b=3 G@enolne)
( olv@") ow) ) = ow), Om) |
same
wil iahiomtaaennsee
ga: To): QT log 2
Tica ey
| oln) , O(n?) =>_Time complexity = Olt)
regs cn) seem a Cp)
v Cad
egos a=2, b= 2, c= OU)
L
| ye? = OD) =
Time complenity = Ov)
leq4: Tin)= 8T/n\ + v3
‘ \2? log
2
cos eg be ce oe
I Uogn 7
| lg \
| on SO) Soe)
\logn J
|
[ On?)
Master thenvem does not work en logarithmic tem
! Ignove Logn
| ln), (nb) 5 ignore Log)
[ “Tine _complenity =O (+P Loy) forlint (2 15 ivi 2eN; 114)
{ {
[ for lint jets jee ts j+t)
LE <
| NOU) work here
}
[
| sa” = 14+2+3+-—+ Jn
An (Jn+1) = N+ {iN
a 2
{
Soa)
Peo sl for (int j=4s i4=Ni itt)
{
foLint jets jects jeeo)
flow
301":
= dog U0) t log (2) 4-- + log Cn)
= Log (11) < oq, Cu") ex _Nlog N
SO favigAl a Se
3 | forint _f=\yien "ri++)
| {
int j-ig jeeNia jet)
4
toa)
]
i
sol”: | itit--+i tm tum) =
;
m=: oN no. of exetuctt ong 6 inne loop
t
a for_some_i
Time = N+ N+ Ne -- tN
2 a N
SSN a Ee eat)
T so 4 NJ
Ne ie
| | é
| Son)
s ve i i (Cu tog N
ppd { int powex Cnt a, int of
| if Cb) stew 45 ae
int_termp = power (a,b/>) * power abo) 5
(by-9 21) temp* = as
etusin temp +
If sof Tin) = 2T[g\ + 0
a
4
2
APO FED A
ae
eo t
wy
L6G
Tine compl = OlAegn) eo
a ||
|
-
on), OW} 060500)
e
—
Time complex = ow)
PpS
int power (int a_, int b) {
it Ub) xetun 1:
int temp > poms (a,//) ;
temp = temp * temp:
if (bea 2= 1) demp=Q
Setwun temp
|
40!"
Tin) = To) + OU)
a
ye! = Vp? = 4 ou)
Same clog n
‘Time complexity = OUoy ) :
