Teh­tä­vä:
Sar­jal­le Θ-mer­kin­tä hel­pos­ti

Ly­hyt Math­Check-oh­je (uu­teen vä­li­leh­teen)

Al­go­rit­mien suo­ri­tus­ky­vyn ana­lyy­sis­sa tu­lee usein las­ket­ta­vak­si muo­toa `f(1)``+``f(2)``+``...``+``f(n)` ole­van sar­jan sum­ma, mis­sä `0``<=``f(1)` ja `f(x)``<=``f(y)` ai­na kun `1``<=``x``<=``y``<=``n`. Sar­jan al­ku­koh­ta voi ol­la myös esi­mer­kik­si `0` ja lop­pu­koh­ta esi­mer­kik­si `n-1`. Jos­kus sum­man tark­ka ar­vo on help­po las­kea, mut­ta usein se on toi­vot­to­man vai­keaa. Al­go­rit­mien ana­lyy­sis­sa ei kui­ten­kaan juu­ri kos­kaan tar­vi­ta tark­kaa ar­voa, vaan `Theta`-mer­kin­nän tark­kuus riit­tää. Täs­sä teh­tä­väs­sä opet­te­lem­me hel­pon ki­kan, jo­ka toi­mii mel­kein (mut­ta ei ai­van) ai­na ja jo­ka tuot­taa vas­tauk­sen sil­lä tark­kuu­del­la.

Käyt­tö­lu­pa­eh­to

Poh­ti­kaam­me aluk­si het­ki, mik­si juu­ri tuon muo­toi­set sar­jat ovat ylei­siä. Usein al­go­rit­mis­sa on sil­muk­ka, jo­ka kä­sit­te­lee tau­lu­kon tms. osaa, jo­ka kas­vaa kier­ros kier­rok­sel­ta. Esi­mer­kik­si in­ser­tion-sortin pää­sil­mu­kas­sa si­joi­te­taan al­kio pai­kal­leen osa­tau­luk­koon, jon­ka ko­ko on en­sim­mäi­sel­lä kier­rok­sel­la 1, toi­sel­la kier­rok­sel­la 2 ja niin edel­leen, kun­nes se on vii­mei­sel­lä kier­rok­sel­la yh­tä pie­nem­pi kuin `n` eli ko­ko tau­lu­kon ko­ko. Osa­tau­luk­koa se­la­taan lo­pus­ta al­kaen ja sen al­kioi­ta siir­re­tään yk­si as­kel oi­keal­le, kun­nes uu­den al­kion paik­ka on löy­ty­nyt. Huo­noim­mas­sa ta­pauk­ses­sa jou­du­taan se­laa­maan ko­ko osa­tau­luk­ko. Huo­noim­man ta­pauk­sen työ­mää­rä on siis yk­sit­täi­sel­lä kier­rok­sel­la suo­raan ver­ran­nol­li­nen osa­tau­lu­kon ko­koon ja yh­teen­sä suo­raan ver­ran­nol­li­nen kä­si­tel­tä­vien osa­tau­lu­koi­den ko­ko­jen sum­maan eli lu­kuun `1``+``2``+``...``+``(n-1)`.

En­tä jos tau­lu­kon tms. osa ei kas­va­kaan kier­ros kier­rok­sel­ta, vaan vä­he­nee kier­ros kier­rok­sel­ta? Vas­tausSil­loin ta­ka­pe­rin kään­net­ty eli lo­pus­ta al­kuun las­ket­tu sar­ja täyt­tää eh­dot. Sen sum­ma on sa­ma kuin al­ku­pe­räi­sen sar­jan sum­ma, jo­ten tä­män teh­tä­vän kik­kaa voi käyt­tää.

Kos­ka ajan ja muis­tin ku­lu­tus ei­vät voi ol­la ne­ga­tii­vi­sia, voim­me olet­taa, et­tä en­sim­mäi­nen ter­mi on vä­hin­tään 0. Toi­si­naan tä­mä eh­to rik­kou­tuu näen­näi­ses­ti. On esi­mer­kik­si var­sin ta­val­lis­ta, et­tä sil­mu­kan yh­del­lä kier­rok­sel­la teh­tä­vä työ­mää­rä on `Theta(log n)`. Jos en­sim­mäi­sel­lä kier­rok­sel­la kä­si­tel­lään tyh­jää tie­to­ra­ken­net­ta, sar­ja al­kaa `log 0 + ...` eli en­sim­mäi­nen ter­mi on `-oo`. Täl­löin en­sim­mäi­nen ter­mi ei kui­ten­kaan ku­vas­ta to­del­lis­ta työ­mää­rää. `Theta`-mer­kin­nän mää­ri­tel­mä sal­lii en­sim­mäi­sen ja toi­sen ter­min (it­se asias­sa min­kä ta­han­sa kiin­teän mää­rän ter­me­jä) ol­la mi­tä ta­han­sa; vaa­di­taan ai­noas­taan, et­tä on ole­mas­sa jo­kin ra­ja, jos­ta al­kaen ter­mit ku­vaa­vat kas­vu­vauh­tia oi­kein. Täs­tä syys­tä en­sim­mäi­nen ter­mi saat­taa ol­la ihan hum­puu­kia.

Toi­saal­ta sa­mas­ta syys­tä `Theta`-mer­kin­nän mää­ri­tel­mä sal­lii jät­tää sar­jan alus­ta yh­den tai kak­si ter­miä pois. Niin­pä, jos `f(0)``>=``0` tai `f(1)``>=``0` ei pä­de, on lu­val­lis­ta aloit­taa sar­ja ter­mis­tä `f(1)` tai `f(2)`, tai vaik­ka ter­mis­tä `f(37)`.

Saa­ko ne­ga­tii­vi­set ter­mit jät­tää pois seu­raa­vien sar­jo­jen sum­man `Theta`-mer­kin­tää las­ket­taes­sa? Mik­si saa tai mik­si ei saa?

• `-2n``+``-(2n-1)``+``...``+``-1``+``0``+``1``+``...``+``n` /*Ne­ga­tii­vis­ten ter­mien mää­rä ei ole kiin­teä, vaan riip­puu #<i#>n#</i#>:stä.*/ only_no_yes_on ok_text Oi­kein! hide_expr 1=

  	kyl­lä
  	ei

  tai
• `-200``+``-199``+``...``+``-1``+``0``+``1``+``...``+``n` /*Ne­ga­tii­vis­ten ter­mien mää­rä on kiin­teä 200. Se ei rii­pu #<i#>n#</i#>:stä.*/ only_no_yes_on ok_text Oi­kein! hide_expr 1=

  	kyl­lä
  	ei

  tai

Kos­ka sil­mu­kan kä­sit­te­le­mä tie­to­ra­ken­ne tyy­pil­li­ses­ti kas­vaa kier­ros kier­rok­sel­ta, ja kos­ka isom­man tie­to­ra­ken­teen kä­sit­te­lyyn me­nee tyy­pil­li­ses­ti enem­män ai­kaa kuin pie­nem­män, `f(1)``<=``f(2)``<=``...``<=``f(n)` pä­tee tyy­pil­li­ses­ti. Tu­lem­me tar­vit­se­maan hie­man vah­vem­paa ole­tus­ta

`f(2/2)``<=``f(3/2)``<=``...``<=``f((2n)/2)`.

Tä­mä ole­tus on kui­ten­kin köm­pe­löä muo­toa. Suo­ri­tus­ai­kaa ku­vaa­maan käy­te­tyt funk­tiot nou­dat­ta­vat yleen­sä yk­sin­ker­tai­sem­paa, vie­lä vah­vem­paa ole­tus­ta: ne ovat kas­va­via reaa­li­lu­ku­vä­lil­lä `1``<=``x``<=``n`. Alus­sa an­net­tu ole­tus sa­noo juu­ri tä­män.

Tar­kas­tel­ta­va sar­ja ei kui­ten­kaan ai­na ole to­del­li­ses­ta al­go­rit­mis­ta pe­räi­sin, ja al­go­rit­meis­sa­kin saat­taa esiin­tyä poik­keuk­sia. Sik­si on syy­tä ai­na aloit­taa var­mis­tau­tu­mal­la, et­tä eh­dot to­del­la­kin pä­te­vät, ken­ties sen jäl­keen kun alus­ta on jä­tet­ty yk­si tai kak­si ter­miä pois.

Pä­te­vät­kö eh­dot seu­raa­vil­le sar­joil­le?

`0^2``+``1^2``+``2^2``+``...``+``n^2` only_no_yes_on ok_text Oi­kein! hide_expr 1=

	Eh­dot pä­te­vät.
	Eh­dot ei­vät pä­de, mut­ta as­tu­vat voi­maan jät­tä­mäl­lä alus­ta enin­tään kak­si ter­miä pois.
	Kum­pi­kaan edel­li­sis­tä ei pä­de.

tai

`(0+(-1)^0)``+``(1+(-1)^1)``+``...``+``(n+(-1)^n)` only_no_yes_on ok_text Oi­kein! hide_expr 1=

	Eh­dot pä­te­vät.
	Eh­dot ei­vät pä­de, mut­ta as­tu­vat voi­maan jät­tä­mäl­lä alus­ta enin­tään kak­si ter­miä pois.
	Kum­pi­kaan edel­li­sis­tä ei pä­de.

tai

`(0+(-1)^0)``+``(2+(-1)^1)``+``...``+``(2n+(-1)^n)` only_no_yes_on ok_text Oi­kein! hide_expr 1=

	Eh­dot pä­te­vät.
	Eh­dot ei­vät pä­de, mut­ta as­tu­vat voi­maan jät­tä­mäl­lä alus­ta enin­tään kak­si ter­miä pois.
	Kum­pi­kaan edel­li­sis­tä ei pä­de.

tai

`1 sqrt(-1)``+``3 sqrt(0)``+``...``+``(2n+1)sqrt(n-1)` only_no_yes_on ok_text Oi­kein! hide_expr 1=

	Eh­dot pä­te­vät.
	Eh­dot ei­vät pä­de, mut­ta as­tu­vat voi­maan jät­tä­mäl­lä alus­ta enin­tään kak­si ter­miä pois.
	Kum­pi­kaan edel­li­sis­tä ei pä­de.

tai

Pe­rus­idea

Tä­män teh­tä­vän ki­kas­sa muo­dos­te­taan sar­jan sum­mal­le hy­vin yk­sin­ker­tai­nen ylä­li­ki­ar­vo ja sie­ven­ne­tään se mah­dol­li­sim­man yk­sin­ker­tai­seen `O`-muo­toon. Sit­ten muo­dos­te­taan yk­sin­ker­tai­nen ala­li­ki­ar­vo ja sie­ven­ne­tään se mah­dol­li­sim­man yk­sin­ker­tai­seen `Omega`-muo­toon. Lo­puk­si kat­so­taan, tu­li­ko sa­mat muo­dot. Jos tu­li sa­mat, tu­los on sar­jan sum­mal­le pä­te­vä `Theta`-mer­kin­tä. Jol­lei tul­lut sa­mat, me­ne­tel­mä epä­on­nis­tui. Yleen­sä tu­lee sa­mat.

Ylä­li­ki­ar­vo

Ylä­li­ki­ar­vo muo­dos­te­taan ker­to­mal­la sar­jan vii­mei­nen ter­mi sar­jan ter­mien mää­räl­lä. Tä­mä on ylä­li­ki­ar­vo sar­jan sum­mal­le täs­tä syys­täKas­va­vuus­ole­tuk­sen vuok­si vii­mei­nen ter­mi on ylä­li­ki­ar­vo mil­le ta­han­sa ter­mil­le.. Tee tä­mä sar­jal­le `1^2``+``2^2``+``...``+``n^2`. Ker­to­las­kun tark­ka tu­los on ok_text Oi­kein! f_nodes 5 hide_expr n^3 = , jo­ka on `O(`end_of_answer arithmetic f_nodes 3 hide_expr n^3 = `)`.
tai

Ala­li­ki­ar­vo

Sar­jan sum­mal­le saa­tai­siin ala­li­ki­ar­vo ker­to­mal­la en­sim­mäi­nen ter­mi ter­mien mää­räl­lä, mut­ta se on yleen­sä eri muo­toa kuin ylä­li­ki­ar­vo, jo­ten näin me­ne­tel­len ei pääs­tä ta­voit­tee­seen. Mel­kein ai­na ta­voit­tee­seen vie­vä ala­li­ki­ar­vo saa­daan käyt­tä­mäl­lä kes­kim­mäis­tä ter­miä ala­li­ki­ar­vo­na sar­jan lop­pu­osan jo­kai­sel­le ter­mil­le ja jät­tä­mäl­lä al­ku­osan ter­mit pois. Kes­kim­mäi­nen ter­mi on täs­tä syys­täkas­va­vuus­ole­tuk­sen vuok­si pä­te­vä ala­li­ki­ar­vo lop­pu­osan ter­meil­le. Lu­pa jät­tää al­ku­osan ter­mit pois tu­lee sii­tä, et­tä …Ne ovat ole­tuk­sen `f(1) >= 0` ja kas­va­vuus­ole­tuk­sen mu­kaan ei-ne­ga­tii­vi­sia. Niil­le saa siis käyt­tää ala­li­ki­ar­vo­na nol­laa. Niin­pä nii­den sum­man ala­li­ki­ar­vok­si tu­lee `0``+``0``+``...``+``0``=``0`.

Tar­kas­tel­laan en­sin ti­lan­net­ta, jos­sa en­sim­mäi­nen ter­mi on `f(1)` ja vii­mei­nen `f(n)`. Jos ter­me­jä on pa­ri­ton mää­rä, kes­kim­mäi­nen ter­mi on `f((n+1)/2)` ja sii­tä al­ka­vas­sa lop­pu­osas­sa on `(n+1)/2` ter­miä. Jäl­kim­mäis­tä voi­daan ar­vioi­da alas­päin lau­sek­keel­la `n/2`, ja kas­va­vuu­den an­sios­ta edel­lis­tä voi­daan ar­vioi­da alas­päin lau­sek­keel­la `f(n/2)`. Näin saa­daan ala­li­ki­ar­vo `n/2 f(n/2)`, jo­ka on hel­pom­paa muo­toa kuin muut vaih­to­eh­dot.

Hel­pon muo­tois­ta ala­li­ki­ar­voa `n/2 f(n/2)` voi­daan käyt­tää myös jos ter­me­jä on pa­ril­li­nen mää­rä. Sil­loin kes­ki­koh­ta osuu ter­mien `f(n/2)` ja `f(n/2+1)` vä­liin. Ter­mis­tä `f(n/2+1)` ter­miin `f(n)` on `n/2` ter­miä. Kas­va­vuus­ole­tuk­sen vuok­si nii­den ala­li­ki­ar­vo­na voi käyt­tää `f(n/2)`. Lau­se­ket­ta `n/2 f(n/2)` voi­daan siis käyt­tää ai­na, riip­pu­mat­ta sii­tä, on­ko `n` pa­ril­li­nen vai pa­ri­ton.

Jos en­sim­mäi­nen ter­mi on­kin `f(0)` ja `f(0)``>=``0`, voim­me sil­ti käyt­tää lau­se­ket­ta `n/2 f(n/2)`, kos­ka …Sil­loin `f(0)``+``f(1)``+``...``+``f(n)``>=``f(1)``+``...``+``f(n)``>=``n/2 f(n/2)`.

Täl­lä kei­nol­la sar­jan `1^2``+``2^2``+``...``+``n^2` sum­mal­le saa­daan ala­li­ki­ar­vo ok_text Oi­kein! f_nodes 9 hide_expr n^3/8 = . Kun va­kiot siir­re­tään eteen, saa­daan end_of_answer arithmetic f_nodes 7 hide_expr n^3/8 = *n^`= Omega`(end_of_answer arithmetic f_nodes 3 hide_expr n^3 =).
tai

Tu­los­ten yh­dis­tä­mi­nen

Saim­me sar­jal­le `1^2``+``2^2``+``...``+``n^2` sa­man­muo­toi­set `O`- ja `Omega`-mer­kin­nät, jo­ten sen sum­ma on ok_text Oi­kein! f_nodes 3 hide_expr n^3 = `Theta(``)`.
tai

Har­joi­tel­laan!

Ote­taan seu­raa­vak­si `log 1``+``...``+``log n`. Va­lit­se. ok_text Hy­vä! only_no_yes_on hide_expr 0 = hide_expr 2

	Olen tar­kas­ta­nut, et­tä en­sim­mäi­nen ter­mi on vä­hin­tään 0.
	Olen tar­kas­ta­nut, et­tä `log(x)` on kas­va­va vä­lil­lä `1``<=``x``<=``n`.

tai

Sar­jan sum­man ylä­li­ki­ar­vok­si tu­lee ok_text Oi­kein! f_nodes 4 hide_expr n log n = , jo­ka on end_of_answer arithmetic f_nodes 4 hide_expr n log n = `O(``)`.
tai

Sar­jan sum­man ala­li­ki­ar­vok­si tu­lee ok_text Oi­kein! f_nodes 17 hide_expr n/2 log n/2 =
=n log n -.
Kos­ka riit­tää ot­taa huo­mioon eni­ten mer­kit­se­vä ter­mi, sum­ma on
end_of_answer arithmetic f_nodes 4 hide_expr n log n = `Omega(``)`.
tai

Niin­pä `log 1``+``...``+``log n = Theta(`ok_text Oi­kein! f_nodes 4 hide_expr n log n = `)`.
tai

En­tä jos pi­tää­kin las­kea `log 1``+``...``+``log (n-1)`? Se­hän on `(log 1``+``...``+``log n) - log n`, mis­sä sul­ku­jen si­säl­tö tut­kit­tiin edel­lä. Edel­lä saa­tu vas­taus on enem­män mer­kit­se­vää muo­toa kuin `log n`, jo­ten `-log n` voi­daan jät­tää pois. Saa­daan siis sa­ma vas­taus kuin edel­lä. Help­poa! Muis­ta kui­ten­kin, et­tä vä­hem­män mer­kit­se­vän ter­min saa jät­tää pois vain kiin­teän mää­rän ker­to­ja. On oi­kein pää­tel­lä, et­tä kos­ka `log 1` ja `log 2` ovat va­kioi­ta ja sik­si mer­kit­se­vät vä­hem­män kuin `log n`, ne saa jät­tää pois ja siis

`Theta(log 1``+``...``+``log n)``=``Theta(log 3``+``...``+``log n)` .

Ei kui­ten­kaan oli­si oi­kein tois­taa tä­mä päät­te­ly kol­men pis­teen yli ja to­de­ta, et­tä

`Theta(log 1``+``...``+``log n) color(red)(= Theta(log n))` .

Kä­si­tel­lään seu­raa­vak­si hie­man han­ka­lam­pi ta­paus:

`5 sqrt(1)``+``7 sqrt(2)``+``...``+``(2n-1)sqrt(n-2)`.

Kos­ka ha­luam­me ai­na lo­pul­ta mah­dol­li­sim­man yk­sin­ker­tai­sen muo­don, va­lit­sem­me in­dek­soin­nin si­ten, et­tä ne­liö­juu­ren al­le tu­lee in­dek­si sel­lai­se­naan. Tä­hän pääs­tään, kun va­li­taan ok_text Oi­kein! f_nodes 8 hide_expr (2i+3)sqrt(i) = `f(i) =`sqrt(i). Sil­loin pie­nim­mäk­si in­dek­sik­si tu­lee 1 ja suu­rim­mak­si end_of_answer arithmetic f_nodes 3 hide_expr n-2 = .
tai

Jot­ta sar­jan vii­mei­ses­sä ter­mis­sä oli­si ne­liö­juu­ren al­la vain `n`, li­sääm­me sar­jan lop­puun ok_text Oi­kein! /*Huo­maa, et­tä nyt pi­tää li­sä­tä enem­män kuin yk­si ter­mi, jot­ta li­säys­ten jäl­keen­kin lau­se­ke oli­si muo­toa `f(1)``+``f(2)``+``...``+``f(`jo­tain`)`.*/ f_nodes 19 hide_expr (2n+1)sqrt(n-1) + (2n+3)sqrt(n) =
.
Rat­kai­sem­me siis eri sar­jaa kuin alun pe­rin teh­tä­väk­si saim­me. Toi­vee­nam­me on, et­tä lo­puk­si voim­me jät­tää nyt li­sä­tyn pois sil­lä pe­rus­teel­la, et­tä se on vä­hem­män mer­kit­se­vää muo­toa kuin saa­tu sar­jan sum­ma. Jos niin käy, niin muun­ta­mam­me sar­jan rat­kai­su pä­tee myös al­ku­pe­räi­sel­le.
tai

Täs­tä eteen­päin tar­kas­tel­laan sar­jaa, jo­hon ym. ter­mit on li­sät­ty, kun­nes toi­sin sa­no­taan. ok_text Hy­vä, niin pi­tää­kin! only_no_yes_on hide_expr 0 = hide_expr 2

	Olen tar­kas­ta­nut, et­tä en­sim­mäi­nen ter­mi on vä­hin­tään 0.
	Olen tar­kas­ta­nut, et­tä `f(x)` on kas­va­va sil­lä vä­lil­lä jo­ta nyt käy­te­tään.

tai

Äs­kei­sel­lä re­sep­til­lä ylä­li­ki­ar­vok­si saa­daan ok_text Oi­kein! f_nodes 10 hide_expr n(2n+3)sqrt(n) =
end_of_answer arithmetic f_nodes 6 hide_expr n^2 sqrt n =`= O(``)`.
tai

Äs­kei­sel­lä re­sep­til­lä ala­li­ki­ar­vok­si saa­daan ok_text Oi­kein! f_nodes 12 hide_expr (n/2)(n+3)sqrt(n/2) =
end_of_answer arithmetic f_nodes 6 hide_expr n^2 sqrt n =`= Omega(``)`.
tai

Mo­lem­mis­ta tu­li sa­ma muo­to, ja se on mer­kit­se­väm­pi kuin se mi­kä edel­lä li­sät­tiin. Niin­pä edel­lä li­sä­tyt voi pois­taa muo­don muut­tu­mat­ta. Kaik­kiaan saim­me tu­lok­sek­si `5 sqrt(1)``+``7 sqrt(2)``+``...``+``(2n-1)sqrt(n-2)``=` ok_text Oi­kein! f_nodes 6 hide_expr n^2 sqrt n =
`Theta(``)`.
tai

Kik­ka ei toi­mi ai­na

Ote­taan lo­puk­si ta­paus, jos­sa kik­ka ei toi­mi: `4^1``+``4^2``+``...``+``4^n`. Äs­kei­sel­lä re­sep­til­lä ylä­li­ki­ar­vok­si saa­daan ok_text Oi­kein! f_nodes 5 hide_expr n*4^n =
end_of_answer arithmetic f_nodes 5 hide_expr n*4^n =`= O(``)`.
tai

Äs­kei­sel­lä re­sep­til­lä ala­li­ki­ar­vok­si saa­daan ok_text Oi­kein! f_nodes 9 hide_expr (n/2)*4^(n/2) =
end_of_answer arithmetic /*Jär­jes­tä eks­po­nen­tik­si `n` ei­kä `n/2`. Se on­nis­tuu po­tens­si­las­kun sään­nöil­lä.*/ f_nodes 5 hide_expr n*4^(n/2) =`= Omega(``)`.
tai

Ne ei­vät ole sa­maa muo­toa. Po­tens­si­las­kun kan­ta­lu­ku ei ole va­kio­ker­roin, jon­ka saa pois­taa tai vaih­taa yk­kö­sek­si `Theta`-mer­kin­tää käy­tet­täes­sä. (Jos sai­si, voi­sim­me joh­taa `2^n color(red)(= Theta(1^n) = Theta(1))` eli var­sin no­peas­ti kas­va­va funk­tio oli­si sa­maa muo­toa kuin funk­tio, jo­ka ei kas­va lain­kaan!)

Saam­me las­ket­tua tä­män sum­man tar­kas­ti te­ke­mäl­lä sii­tä yh­tä­lön. Mer­kit­sem­me `x``=``4^1``+``4^2``+``...``+``4^n`. Ker­to­mal­la mo­lem­mat puo­let 4:llä saa­daan ok_text Oi­kein! f_nodes 3 hide_expr 4x =
`=`end_of_answer arithmetic f_nodes 3 hide_expr 4^2=`+ ... +`end_of_answer arithmetic f_nodes 5 hide_expr 4^(n+1)=.
tai

Vä­hen­tä­mäl­lä täs­tä `x``=``4^1``+``...``+``4^n` (siis va­sem­mal­ta puo­lel­ta vä­hen­ne­tään `x` ja oi­keal­ta `4^1``+``...``+``4^n`) saa­daan ok_text Oi­kein! f_nodes 3 hide_expr 3x =
`=`end_of_answer arithmetic f_nodes 7 hide_expr 4^(n+1) - 4=
tai

ok_text Oi­kein! f_nodes 9 hide_expr (4^(n+1) - 4)/3 = Niin­pä `x =``= Theta(`end_of_answer arithmetic /*Saat eks­po­nen­tis­ta yk­kö­sen pois muun­ta­mal­la sen ker­to­las­kuk­si, jol­loin sen vai­ku­tus muut­tuu va­kio­ker­toi­mek­si, jon­ka voi pois­taa.*/ f_nodes 3 hide_expr 4^n =`)`.
tai

Tar­kan muo­don ver­taa­mi­nen edel­lä joh­det­tui­hin ylä- ja ala­li­ki­ar­voi­hin ker­too, et­tä kum­pi­kin li­ki­ar­vo on huo­no. Täs­sä ta­pauk­ses­sa syy­nä on se, et­tä sar­jan ter­mit kas­va­vat var­sin no­peas­ti. Täl­lai­sia sar­jo­ja esiin­tyy al­go­rit­mien ana­lyy­sis­sa, mut­ta sil­loin al­go­rit­mi on ai­na­kin joil­la­kin suu­ril­la syöt­teil­lä toi­vot­to­man hi­das. Yleen­sä py­ri­tään löy­tä­mään no­peam­pia al­go­rit­me­ja jos mah­dol­lis­ta. Sik­si tä­män teh­tä­vän kik­ka toi­mii käy­tän­nön al­go­rit­mien ana­lyy­sis­sa mel­kein ai­na.

Lo­puk­si

Edel­lä käy­tet­ty ylä­li­ki­ar­von muo­dos­ta­mis­ta­pa on hy­vin yk­sin­ker­tai­nen ja kan­nat­taa osa­ta. Myös ala­li­ki­ar­von muo­dos­ta­mis­ta­pa kan­nat­taa muis­taa, sil­lä se on laa­jas­ti käyt­tö­kel­poi­nen. Se oli seu­raa­va:

1. Sar­ja jaet­tiin kah­tia pie­niin ja suu­riin ter­mei­hin.
2. Jo­kai­sen pie­nen ter­min ala­li­ki­ar­vo­na käy­tet­tiin nol­laa.
3. Jo­kai­sen suu­ren ter­min ala­li­ki­ar­vo­na käy­tet­tiin kes­kim­mäis­tä ter­miä.

Ylä- ja ala­li­ki­ar­vot ovat hyö­dyl­li­siä muual­la­kin kuin sar­jois­sa. Ote­taan jääh­dyt­te­lyk­si edel­li­siä vain etäi­ses­ti muis­tut­ta­va teh­tä­vä. Jos ym­py­rän sä­de on `r`, niin sen pin­ta-ala on `pi r^2`. Ohei­sen ku­van avul­la on help­po pää­tel­lä näinYm­py­rän ym­pä­ri piir­re­tyn ne­liön pin­ta-ala on `4r^2`. Sii­hen mah­tuu 8 sa­man­lais­ta kol­mio­ta, jo­ten kol­mion pin­ta-ala on `(4r^2)/8``=``1/2 r^2` ja ym­py­rän si­sään vi­nos­ti piir­re­tyn ne­liön pin­ta-ala on `4*1/2 r^2``=``2 r^2`., et­tä
only_no_yes_on ok_text Oi­kein! f_nodes 1 hide_expr 2 =`<``pi``<`end_of_answer arithmetic f_nodes 1 hide_expr 4 =. tai