Teh­tä­vä:
Isot O, Ω ja Θ

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

Al­go­rit­mien no­peus, muis­tin ku­lu­tus tai muu re­surs­sien ku­lu­tus saat­taa riip­pua syöt­teen koos­ta mo­nel­la eri ta­val­la. On ta­val­lis­ta il­mais­ta tä­mä riip­pu­vuus isol­la O-, Ω- tai Θ-mer­kin­näl­lä. Täs­sä teh­tä­väs­sä tu­tus­tu­taan nii­hin. Konk­re­tian vuok­si pu­hum­me ajan ku­lu­tuk­ses­ta, mut­ta kä­si­tel­tä­vät asiat pä­te­vät myös muis­tin jne. ku­lu­tuk­seen.

Esi­merk­ki

Aloi­tam­me esi­mer­kil­lä, jo­ka ha­vain­nol­lis­taa va­lin­ta­ti­lan­net­ta, jon­ka kal­tai­sia tu­lee oh­jel­moin­nis­sa usein vas­taan. Teh­tä­vään on tar­jol­la kak­si vaih­to­eh­tois­ta al­go­rit­mia. Al­go­rit­mi A on yk­sin­ker­tai­nen ja help­po oh­jel­moi­da. Sen mil­li­se­kun­tei­na mi­tat­tu ajan ku­lu­tus syöt­teen koon `n` funk­tio­na nou­dat­taa lau­se­ket­ta `n^2/50+1`. (Yk­si se­kun­ti on 1000 mil­li­se­kun­tia.) Al­go­rit­mi B on mo­ni­mut­kai­nen ja vai­kea oh­jel­moi­da. Sen mil­li­se­kun­tei­na mi­tat­tu ajan ku­lu­tus syöt­teen koon `n` funk­tio­na nou­dat­taa lau­se­ket­ta `n log n+10`.

Nap­pia klik­kaa­mal­la saat nä­ky­viin A:n ajan ku­lu­tuk­sen ku­vaa­jan vih­reäl­lä ja B:n pu­nai­sel­la. Math­Check piir­tää ku­vaa­jan al­kaen `n`:n ar­vos­ta 0 laa­ti­kos­sa ole­vaan ar­voon saak­ka. Voit vaih­taa laa­ti­kon ar­von. Pik­ku­ruu­dus­ta voit ti­la­ta 0,3 se­kun­tia edus­ta­van si­ni­sen vii­van.
real n draw_function 0 20; n^2/50+1; n log n + 10 tai

Va­lit­se oi­keat vaih­to­eh­dot. ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 2

	Syöt­teen ko­ko voi ol­la vain luon­nol­li­nen lu­ku, mut­ta käy­rät käyt­tä­vät `n`:n ar­voi­na mui­ta­kin lu­ku­ja.
	Laa­ti­kos­sa val­mii­na ole­van ar­von tuot­ta­mat käy­rät riit­tä­vät A:n ja B:n ver­taa­mi­seen.
	A on ai­na no­peam­pi kuin B.
	Niil­lä `n` joil­la B on hi­taam­pi kuin A, B ku­lut­taa al­le 0,3 se­kun­tia.

tai

Kir­joi­ta tau­luk­koon A:n ja B:n ajan ku­lu­tus an­ne­tuil­la `n`:n ar­voil­la.

`n`	1	10	100	1000	10000
A	only_no_yes_on ok_text Oi­kein! f_nodes 5 hide_expr (1^2)/50+1 =	end_of_answer arithmetic f_nodes 1 hide_expr (10^2)/50+1 =	end_of_answer arithmetic f_nodes 1 hide_expr (100^2)/50+1 =	end_of_answer arithmetic f_nodes 1 hide_expr (1000^2)/50+1 =	end_of_answer arithmetic f_nodes 1 hide_expr (10000^2)/50+1 =
B	end_of_answer arithmetic f_nodes 1 hide_expr 1 log 1 + 10 =	end_of_answer arithmetic f_nodes 1 hide_expr 10 log 10 + 10=	end_of_answer arithmetic f_nodes 1 hide_expr 100 log 100 + 10 =	end_of_answer arithmetic f_nodes 1 hide_expr 1000 log 1000 + 10 =	end_of_answer arithmetic f_nodes 1 hide_expr 10000 log 10000 + 10 =

tai

Kum­pi al­go­rit­mi kan­nat­taa va­li­ta seu­raa­vis­sa ti­lan­teis­sa? Vas­taa A tai B.

• Al­go­rit­mia tul­laan käyt­tä­mään sa­mas­sa oh­jel­mas­sa sa­ta ker­taa. Yh­del­lä ker­taa syö­te­ko­ko on 1000 ja muil­la ker­roil­la 10. only_no_yes_on ok_text Oi­kein! /*A hä­viää syö­te­kool­la 1000 niin pal­jon, et­tä syö­te­kool­la 10 saa­vu­te­tut 99 voit­toa ei­vät rii­tä ot­ta­maan B:n etu­mat­kaa kiin­ni.*/ hide_expr f_nodes 1 B =
  tai
• Al­go­rit­mia aje­taan hy­vin mon­ta ker­taa, ja suu­rin kos­kaan esiin­ty­vä syö­te on kool­taan enin­tään 100. only_no_yes_on ok_text Oi­kein! /*A:n pa­rem­pi no­peus pie­nil­lä syöt­teil­lä on täs­sä ti­lan­tees­sa rat­kai­se­va etu.*/ hide_expr f_nodes 1 A =
  tai
• Kän­ny­kän käyt­tä­jä malt­taa odot­taa vas­taus­ta kor­kein­taan 0,5 se­kun­tia. Las­ken­taan me­nee tä­män al­go­rit­min käyt­tä­män ajan li­säk­si 0,4 se­kun­tia muu­hun. only_no_yes_on ok_text Oi­kein! /*A:lla saa­daan kä­si­tel­tyä isom­pia syöt­tei­tä al­go­rit­mil­le jää­väs­sä 0,1 se­kun­nis­sa.*/ hide_expr f_nodes 1 A =
  tai
• Seu­raa­vas­sa käyt­tö­jär­jes­tel­mä­ver­sios­sa muun las­ken­nan ai­ka saa­tiin no­peu­tet­tua 0,2 se­kun­tiin. Muu­ten ti­lan­ne on sa­ma kuin edel­lä. only_no_yes_on ok_text Oi­kein! /*B:llä saa­daan kä­si­tel­tyä isom­pia syöt­tei­tä al­go­rit­mil­le jää­väs­sä 0,3 se­kun­nis­sa.*/ hide_expr f_nodes 1 B =
  tai
• Al­go­rit­mi si­joi­te­taan yleis­käyt­töi­seen kir­jas­toon. Sen käy­tös­sä esiin­ty­vis­tä syö­te­kois­ta ei tie­de­tä mi­tään. only_no_yes_on ok_text Oi­kein! /*Pie­nil­lä syöt­teil­lä A oli­si pa­rem­pi, mut­ta myös B on niil­lä var­sin no­pea. Suu­ril­la syöt­teil­lä A on rat­kai­se­vas­ti huo­nom­pi.*/ hide_expr f_nodes 1 B =
  tai

Vas­tauk­sen on tul­ta­va 3 se­kun­nis­sa. Suu­rin syö­te­ko­ko, jos­ta A sel­viää sii­nä ajas­sa, on only_no_yes_on ok_text Oi­kein! /*Syö­te­ko­ko on ai­na ko­ko­nais­lu­ku.*/ hide_expr f_nodes 1 387 = . Suu­rin syö­te­ko­ko, jos­ta B sel­viää sii­nä ajas­sa, on end_of_answer arithmetic hide_expr f_nodes 1 997 = .
tai

Toi­vot­ta­vas­ti nä­mä esi­mer­kit riit­ti­vät va­kuut­ta­maan, et­tä vaik­ka B on vai­kea to­teut­taa ja pie­nil­lä syöt­teil­lä hi­taam­pi kuin A, se on sil­ti yleen­sä pa­ras va­lin­ta. A on sel­väs­ti pa­ras vain jos on var­maa, et­tä suu­rin kos­kaan esiin­ty­vä syö­te on pie­ni. Yleen­sä syö­te­ko­ko­ja kos­ke­va tie­to on puut­teel­lis­ta. Yk­si­kin iso syö­te saat­taa vie­dä A:lla niin pal­jon ai­kaa, et­tä se rat­kai­see ko­ko­nais­ajan­ku­lu­tuk­sen B:n eduk­si.

B hä­viää kun kaik­ki syöt­teet ovat pie­niä, mut­ta pie­nil­lä syöt­teil­lä kum­pi­kin al­go­rit­mi ku­lut­taa ai­kaa niin vä­hän, et­tä sil­lä ei yleen­sä ole mer­ki­tys­tä. Poik­keus täs­tä on, et­tä jos al­go­rit­mia kut­su­taan mon­ta ker­taa ja ai­na pie­nel­lä syöt­teel­lä, niin B on mer­kit­tä­väs­ti hi­taam­pi.

Toi­sin kuin voi­si luul­la, tie­to­ko­nei­den no­peu­den kas­vu yleen­sä li­sää ei­kä vä­hen­nä nii­den ti­lan­tei­den mää­rää, jois­sa kan­nat­taa va­li­ta B, kos­ka se kas­vat­taa si­tä syö­te­ko­koa jon­ka kum­pi­kin al­go­rit­mi eh­tii kä­si­tel­lä en­nen kuin ajan ku­lu­tus käy liian suu­rek­si.

Mo­ti­vaa­tio

Jos yh­den oh­jel­man ajan ku­lu­tus on `20 n log n + 5` ja toi­sen `15 n log n + 5`, niin on sel­vää, et­tä jäl­kim­mäi­nen on no­peam­pi. Va­li­tet­ta­vas­ti ti­lan­ne on erit­täin har­voin näin sel­vä.

En­sik­si, ajan ku­lu­tus riip­puu usein syöt­teen koon li­säk­si syöt­teen laa­dus­ta. Esi­mer­kik­si insertion-sort on mel­kein jär­jes­tyk­ses­sä ole­val­le isol­le tau­lu­kol­le pal­jon no­peam­pi kuin sa­man­ko­koi­sel­le täy­sin se­kai­ses­sa jär­jes­tyk­ses­sä ole­val­le tau­lu­kol­le. Sil­loin tä­män kal­tai­nen lau­se­ke pys­tyy esit­tä­mään ajan ku­lu­tuk­sen vain tie­tyn­lai­sil­le syöt­teil­le. Usein ajan ku­lu­tus esi­te­tään sa­man­ko­koi­sis­ta syöt­teis­tä sil­le, jol­la ai­kaa ku­luu eni­ten. Toi­si­naan esi­te­tään sa­man­ko­kois­ten syöt­tei­den ajan ku­lu­tuk­sien kes­ki­ar­vo.

Toi­sek­si, ajan ku­lu­tus­ta tar­kas­ti ku­vaa­va funk­tio on usein mo­ni­mut­kai­nen. Se voi ol­la esi­mer­kik­si `8n^2 - 2 n |__log n__| + 12 n + 7`. Mel­kein ai­na on kui­ten­kin ole­mas­sa yk­sin­ker­tai­nen funk­tio, jo­ka tuot­taa suu­ril­la `n`:n ar­voil­la li­ki­main sa­mat tu­lok­set. Täs­sä esi­mer­kis­sä `8n^2` on sel­lai­nen funk­tio. Täl­lai­nen yk­sin­ker­tai­nen funk­tio tuot­taa yleen­sä riit­tä­vän tar­kan tu­lok­sen, kos­ka ajan ku­lu­tus­ta suu­ril­la syöt­teil­lä ei yleen­sä tar­vit­se tie­tää ai­van tark­kaan, ja pie­nil­lä syöt­teil­lä riit­tää yleen­sä tie­to et­tä se on pie­ni.

Kol­man­nek­si, usein tie­däm­me esi­mer­kik­si, et­tä ajan ku­lu­tus suu­ril­la syöt­teil­lä on li­ki­main `c n log n`, mis­sä `c` on jo­kin va­kio, mut­ta em­me yleen­sä tie­dä `c`:n ar­vos­ta juu­ri mi­tään sil­loin kun tie­toa tar­vit­tai­siin. Se riip­puu käy­tös­sä ole­vas­ta tie­to­ko­nees­ta, oh­jel­moin­ti­kie­les­tä, kään­tä­jäs­tä tai tul­kis­ta, käyt­tö­jär­jes­tel­män ver­sios­ta, al­go­rit­min to­teu­tuk­sen yk­si­tyis­koh­tien va­lin­nas­ta, muis­ta tie­to­ko­nees­sa sa­man­ai­kai­ses­ti suo­ri­tet­ta­vis­ta oh­jel­mis­ta ja mah­dol­li­ses­ti jo­pa akun va­raus­ti­las­ta.

Kun oh­jel­ma on to­teu­tet­tu, `c`:lle voi­daan usein (mut­ta ei ai­na) saa­da hy­vä li­ki­ar­vo mit­tauk­sil­la. Tä­mä on liian myö­hään, jos oli­sim­me ha­lun­neet tie­don sen päät­tä­mi­sek­si, mi­kä vaih­to­eh­to kan­nat­taa to­teut­taa.

Käy­tän­nös­sä al­go­rit­mi py­ri­tään to­teut­ta­maan niin hy­vin kuin koh­tuul­li­sel­la vai­val­la on­nis­tuu. Yleen­sä sil­lä ta­val­la tu­lee riit­tä­vän hy­vä tu­los, jos al­go­rit­mi on hy­vin va­lit­tu. Jol­lei tu­le, ale­taan et­siä kei­no­ja no­peut­taa to­teu­tus­ta tai muul­la ta­val­la rat­kais­ta on­gel­ma.

Ti­lan­ne on toi­sen­lai­nen sil­loin, kun ver­rat­ta­va­na on kak­si al­go­rit­mia, joi­den ajan ku­lu­tus­ten yk­sin­ker­tai­set li­ki­mää­räi­set funk­tiot ovat eri muo­toa. Ol­koot ne esi­mer­kik­si `c n^2` ja `d n log n`. Kos­ka suo­ri­tus­ajat ei­vät voi ol­la nol­la ei­vät­kä ne­ga­tii­vi­sia, pä­tee `c > 0` ja `d > 0`. Ovat­pa `c` ja `d` mi­tä ta­han­sa po­si­tii­vi­sia reaa­li­lu­ku­ja, on vää­jää­mät­tä ole­mas­sa jo­kin lu­ku, jo­ta suu­rem­mil­la `n`:n ar­voil­la `d n log n``<``c n^2`. Mi­tä suu­rem­pi `d` on ja mi­tä pie­nem­pi `c` on, si­tä suu­rem­pi pie­nin täl­lai­nen lu­ku on. Käy­tän­nön ti­lan­teis­sa pie­nin täl­lai­nen lu­ku on mel­kein ai­na niin pie­ni, et­tä si­tä suu­rem­mat syöt­teet ovat ta­val­li­sia. Täs­tä nyrk­ki­sään­nös­tä on poik­keuk­sia, mut­ta ne ovat har­vi­nai­sia.

Täs­tä ei seu­raa, et­tä ai­na kan­nat­taa va­li­ta al­go­rit­mi, jon­ka ajan ku­lu­tuk­sen muo­to on pa­ras. On esi­mer­kik­si ta­val­lis­ta, et­tä vaik­ka `c n` on­kin muo­dol­taan pa­rem­pi kuin `d n log n`, ero on isoil­la­kin syöt­teil­lä niin pie­ni, et­tä sil­lä ei ole mer­ki­tys­tä. Sen si­jaan `c n^2` on yleen­sä isoil­la syöt­teil­lä niin hi­das, et­tä pa­rem­man vaih­to­eh­don et­si­mi­seen ja to­teut­ta­mi­seen kan­nat­taa pa­nos­taa. Oi­kea joh­to­pää­tös on, et­tä ajan ku­lu­tuk­sen muo­toon kan­nat­taa kiin­nit­tää pal­jon huo­mio­ta.

Va­lit­se oi­kea vaih­to­eh­to. only_no_yes_on ok_text Oi­kein! hide_expr 1=

	Eni­ten mer­kit­se­vä ter­mi il­man va­kio­ker­roin­ta an­taa ai­na riit­tä­vän tar­kan tie­don al­go­rit­min no­peu­des­ta isoil­la syöt­teil­lä.
	Al­go­rit­min no­peu­den sel­vit­tä­mi­nen kan­nat­taa aloit­taa sel­vit­tä­mäl­lä eni­ten mer­kit­se­vä ter­mi il­man va­kio­ker­roin­ta, mut­ta asiaa on yleen­sä vält­tä­mä­tön­tä tut­kia myös tar­kem­mil­la kei­noil­la.
	Eni­ten mer­kit­se­vä ter­mi il­man va­kio­ker­roin­ta an­taa hy­vin usein, mut­ta ei ai­na, riit­tä­vän tar­kan tie­don al­go­rit­min no­peu­des­ta.

tai

Ole­te­taan, et­tä oh­jel­maa aje­taan ai­na sa­mal­la tie­to­ko­neel­la sa­mas­sa käyt­tö­jär­jes­tel­mäs­sä si­ten, et­tä ko­nees­sa ei ole sa­man­ai­kai­ses­ti muu­ta kuor­mi­tus­ta ja kaik­ki fyy­si­set te­ki­jät on va­kioi­tu (ak­ku on ai­na täy­des­sä la­tauk­ses­sa, läm­pö­ti­la on ai­na sa­ma jne.). Ajan ku­lu­tus mi­ta­taan mo­nen­ko­koi­sil­la syöt­teil­lä ja ha­vai­taan, et­tä se on var­sin tar­kas­ti `38 n^3` kun `n >= 100`. Voi­daan­ko pi­tää mel­ko var­ma­na, et­tä `38 n^3` on hy­vä li­ki­ar­vo ajan ku­lu­tuk­sel­le ai­na kun `n >= 100`? /*Ei voi­da, kos­ka ajan ku­lu­tus saat­taa riip­pua syöt­teen laa­dus­ta. Voi ol­la, et­tä toi­sen­lai­sil­la sa­man­ko­koi­sil­la syöt­teil­lä mit­taus­tu­lok­set oli­si­vat­kin var­sin tar­kas­ti vaik­ka `47 n^2` kun `n >= 100`. #<br#>#<br#>Li­säk­si käy­tän­nös­sä on ha­vait­tu 10% suu­ruus­luo­kas­sa ole­vaa vaih­te­lua jo­pa sa­mal­la syöt­teel­lä, vaik­ka kaik­ki mah­dol­li­nen on va­kioi­tu. Käyt­tö­jär­jes­tel­mä saat­taa teh­dä jo­tain taus­tal­la, oh­jel­ma saat­taa eri ajo­ker­roil­la tal­let­taa tu­lok­set eri koh­taan kiin­to­le­vyä ja niin edel­leen.*/ only_no_yes_on ok_text Oi­kein! hide_expr 1=

	ei
	kyl­lä

tai

Mer­kin­nät

Edel­lä ker­ro­tuis­ta syis­tä al­go­rit­mien ana­lyy­sis­sä riit­tää yleen­sä tun­nis­taa eni­ten mer­kit­se­vä ter­mi, esi­mer­kik­si `cn^2` tai `cn log n`, ja il­moit­taa se il­man va­kio­ker­roin­ta `c`. Tä­hän käy­te­tään O-, Ω- ja Θ-mer­kin­tö­jä. Ne lue­taan ”iso oo”, ”iso omega” ja ”iso theta”, kos­ka myös ”pik­ku oo” ja "pik­ku omega” ovat käy­tös­sä sa­man­ta­pai­sis­sa roo­leis­sa. Täs­sä teh­tä­väs­sä opis­ke­lem­me kol­me en­sin mai­nit­tua. Nii­den mer­ki­tys on seu­raa­va:

• `O(n^2)` ajan ku­lu­tus on enin­tään muo­toa `n^2`.
• `Omega(n^2)` ajan ku­lu­tus on vä­hin­tään muo­toa `n^2`.
• `Theta(n^2)` ajan ku­lu­tus on tar­kal­leen muo­toa `n^2`.

Muut mer­kin­nät kuin Θ tar­vi­taan, kos­ka ajan ku­lu­tuk­sen muo­toa ei ai­na pys­ty­tä sel­vit­tä­mään tar­kas­ti ei­kä vält­tä­mät­tä edes ole ole­mas­sa muo­toa, jo­ka pä­ti­si kai­ken­lai­sil­le syöt­teil­le. Esi­mer­kik­si insertion-sortin ajan ku­lu­tus on mel­kein jär­jes­tyk­ses­sä ole­vil­le tau­lu­koil­le muo­toa `c n` ja tyy­pil­li­sil­le tau­lu­koil­le muo­toa `c n^2`. Mil­le­kään tau­lu­koil­le se ei ole pa­rem­pi kuin `c n` ei­kä huo­nom­pi kuin `c n^2`. Sik­si voi­daan sa­noa, et­tä insertion-sortin ajan ku­lu­tus on `Omega(n)` ja `O(n^2)`, mut­ta ei voi­da sa­noa, et­tä se on `Theta(...)`, oli­pa kol­men pis­teen pai­kal­la mi­tä ta­han­sa. Kui­ten­kin voi­daan sa­noa, et­tä se on hi­taim­mil­laan `Theta(n^2)` ja no­peim­mil­laan `Theta(n)`.

Tar­koit­taa­ko ”al­go­rit­mi on hi­taim­mil­laan `Theta(n^2)`” sa­maa kuin ”al­go­rit­min ajan ku­lu­tus on `O(n^2)`”? /*Ei tar­koi­ta. ”Ajan ku­lu­tus on #<i#>O#</i#>(#<i#>n#</i#>#<sup#>2#</sup#>)” lu­paa, et­tä ajan ku­lu­tus ei ole tä­tä suu­rem­pi min­kään­lai­sil­la syöt­teil­lä, mut­ta se ei lu­paa, et­tä on ole­mas­sa syöt­teet joil­la ajan ku­lu­tus on näin suu­ri. ”Al­go­rit­mi on hi­taim­mil­laan Θ(#<i#>n#</i#>#<sup#>2#</sup#>)” lu­paa mo­lem­mat. Niin­pä jos al­go­rit­min ajan ku­lu­tus on ai­na Θ(#<i#>n#</i#> log #<i#>n#</i#>), niin se on #<i#>O#</i#>(#<i#>n#</i#>#<sup#>2#</sup#>) mut­ta ei ole hi­taim­mil­laan Θ(#<i#>n#</i#>#<sup#>2#</sup#>).*/ only_no_yes_on ok_text Oi­kein! hide_expr 1=

	ei
	kyl­lä

tai

Jos `k > h`, niin `n^k` mer­kit­see enem­män kuin `n^h`. Ter­mi `n` mer­kit­see enem­män kuin `sqrt n`, ja `sqrt n` mer­kit­see enem­män kuin `log n`.

Kir­joi­ta sul­ku­jen si­sään mah­dol­li­sim­man yk­sin­ker­tai­nen lau­se­ke si­ten, et­tä väit­tä­mä pä­tee.

ok_text Oi­kein! hide_expr f_nodes 3 n^2 = `7 n log n + 2 n^2 - 5n + 3 = Theta(``)`
tai

ok_text Oi­kein! hide_expr f_nodes 4 n log n = `32 n + 7 n log n - 12 sqrt(n) + 31 = Theta(``)`
tai

ok_text Oi­kein! hide_expr f_nodes 4 n sqrt n = `7n(log n + 3 sqrt(n)) + 18 = Theta(``)`
tai

ok_text Oi­kein! /*Kun su­lut ker­ro­taan au­ki, `n^2`-muo­toi­set ter­mit ku­moa­vat toi­sen­sa ja syn­tyy ter­mi `8n`.*/ hide_expr f_nodes 1 n = `25 + (n+4)^2 + 8log n - n^2 = Theta(``)`
tai

Mit­kä seu­raa­vis­ta pä­te­vät insertion-sortin suo­ri­tus­ajal­le?

ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 2

`O(log n)`	`O(n)`	`O(n sqrt(n))`	`O(n^2)`	`O(n^3)`

tai

ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 2

`Omega(log n)`	`Omega(n)`	`Omega(n sqrt(n))`	`Omega(n^2)`	`Omega(n^3)`

tai

ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 0

`Theta(log n)`	`Theta(n)`	`Theta(n sqrt(n))`	`Theta(n^2)`	`Theta(n^3)`

tai

Mit­kä seu­raa­vis­ta pä­te­vät insertion-sortin hi­taim­man ta­pauk­sen suo­ri­tus­ajal­le?

ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 2

`O(log n)`	`O(n)`	`O(n sqrt(n))`	`O(n^2)`	`O(n^3)`

tai

ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 4

`Omega(log n)`	`Omega(n)`	`Omega(n sqrt(n))`	`Omega(n^2)`	`Omega(n^3)`

tai

ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 1

`Theta(log n)`	`Theta(n)`	`Theta(n sqrt(n))`	`Theta(n^2)`	`Theta(n^3)`

tai

Mit­kä seu­raa­vis­ta pä­te­vät insertion-sortin no­peim­man ta­pauk­sen suo­ri­tus­ajal­le?

ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 4

`O(log n)`	`O(n)`	`O(n sqrt(n))`	`O(n^2)`	`O(n^3)`

tai

ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 2

`Omega(log n)`	`Omega(n)`	`Omega(n sqrt(n))`	`Omega(n^2)`	`Omega(n^3)`

tai

ok_text Teit oi­keat va­lin­nat! only_no_yes_on hide_expr 0 = hide_expr 1

`Theta(log n)`	`Theta(n)`	`Theta(n sqrt(n))`	`Theta(n^2)`	`Theta(n^3)`

tai

Täs­tä tär­keäs­tä asias­ta oli­si pal­jon enem­män­kin sa­not­ta­vaa, mut­ta ei­kö­hän täs­sä ol­lut riit­tä­väs­ti yh­del­le ker­taa.