Megoldások az első gyakorlathoz

1. Rendezzünk kieséses versenyt az elemek között. Azaz hasonlítsunk össze két elemet, a kisebbet dobjuk el, a nagyobbat hasonlítsuk egy új elemhez és ezt ismételgessük, amíg már nincsen új elem. Ami ekkor a kezünkben van, az a legnagyobb elem. Ez n-1 összehasonlítás.
Ennél jobbat nem is várhatunk, mert minden összehasonlítás legfeljebb egy elemet zár ki azok közül, akik még lehetnek legnagyobb elemek. Az elején n jelölt van, a végén egynek kell maradnia. azaz n-1 összehasonlítás kell is.

2. T(n)=3(n-1)+2
(Ezt ellenőrizni is kell: (1) n=1-re jó-e? (2) A rekurziós formulába visszahelyettesitve jó-e?)

3. $T(n)=3^{n-1}+{1\over 2}\cdot {(3^n-1)}$
Ellenőrzés is kell!!!

4. $T(n)= {9\over 5}{n^2}-{{1\over 5}{4^{{\log}_3+1}}}$
Ellenőrzés!!!

5. (a) Ha a program lépésszáma n-nel arányos n méretű feladat estén, akkor az, hogy egy nap alatt megold egy k méretű feladatot, az azt jelenti, hogy egy nap alatt $C\cdot k$ lépést tesz, ahol C>0 egy pozitív konstans. Ha a gép százszor gyorsabb lesz, akkor ezután $100C\cdot k$ lépést bír tenni. Kérdés, hogy mi az az l méretű feladat, amire ez elég. Azaz mi az az l, amire $C\cdot l=100C\cdot k$? Nyilván l=100k.
(b) Hasonlóan gondolkodunk, mint az előbb. Eddig megoldott egy k méretűt egy nap alatt, tehát bírt lépni Ck³ lépést. A gyors gép 100-szor annyit tud, 100Ck³ lépést egy nap alatt. Ez arra az l méretű feladatra elég, ahol Cl³=100Ck³, azaz ahol $l=\sqrt[3]{100}k$.
(c) Hasonlóan: eddig tudott C2^k lépést, most tud 100C2^k lépést. Ez arra az l-re elég, ahol C2^l=100C2^k, azaz az $l=k+{\log}_2 100$.

6. (a) ${\log}_{100} f(n)= {\log}_2 f(n) \cdot {\log}_{100} 2$, vagyis $K_1=K_2={\log}_{100} 2$ választással fennáll $K_1{\log}_{100} f(n)\leq {\log}_2 f(n) \leq K_2{\log}_{100} f(n)$ egyenlőtlenség.
(b) $2^{n+1}=2\cdot 2^n$, vagyis K₁=K₂=2 választással fennáll a $K_12^n\leq 2^{n+1}\leq K_22^n$ egyenlőtlenség.
Másrészt ha 2²ⁿ=O(2ⁿ) lenne, akkor az azt jelentené, hogy van olyan K>0 szám, hogy $2^{2n}\leq K2^n$ lenne, ekkor viszont $2^n\leq K$-nek kellene teljesülnie minden n-re, ami nem lehet.
(c) $max(f(n),g(n))\leq f(n)+g(n)$, másrészt $f(n)+g(n)\leq 2\cdot max(f(n),g(n))$. Ezekből adódik az állítás, a $K_1={1\over 2}$, K₂= 1 választással.

7. A teljes feladatsorban szerepel a megoldás a Rendezés 15. feladatnál.

8. A teljes feladatsorban szerepel a megoldás a Rendezés 43. feladatnál.

9. Benne van a jegyzetben a megoldás.

10. $6n^2-2n+7\leq 6n^2+7\leq 7n^2$, ha $n\geq 3$, azaz K₂=7 jó választás. Másrészt $6n^2-2n+7\geq 6n^2-2n\geq 5n^2$, ha $n\geq 3$, tehát K₁=5 jó lesz.