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 Ck3 lépést. A gyors gép 100-szor annyit tud, 100Ck3 lépést egy nap alatt. Ez arra az l méretű feladatra elég, ahol Cl3=100Ck3, azaz ahol $l=\sqrt[3]{100}k$. (c) Hasonlóan: eddig tudott C2k lépést, most tud 100C2k lépést. Ez arra az l-re elég, ahol C2l=100C2k, 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 K1=K2=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 22n=O(2n) 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}$, K2= 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 K2=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 K1=5 jó lesz.