g = O (f ) <= (+oo); g = Ω (f ) >=(0); g = Θ (f ) =(c>0)
lgn<sqrt(n)<nlg(n)<n<n2<n3<2n<n!   E=lim(n->oo)(f/g)
lg(n!)= Θ (nlg(n))      2lg(n)=n       lgb=c => 2c=b
W(n) = pes, A(n)=oczek zl. czas.
t’=? n’: t’=2n’*t/T(n)
n’=? t’: 2n’=t’*T(n)/t
x szyb, n’: t’=2n’*t/xsz/T(n)
Koszty:
1. Szuk nieuporządk Best 1p, worst np
2. Sekw. Best 1 or 2p, worst 2+(n-1)p, ave A(n) = n/2 +c, c<2
3. Skoki „co k” worst 2+ n/k+(k-1)
5. Min-max worst W(n)=2n-2
6. Min-max3 n jest parzyste, 1szy krok=n/2p, Min;max=n/2-1p
Razem = 3n/2  -2 porównań.
7. Min-max4 T(n)=3/2 n-2, worst >= [3/2 n]-2p
8. 2gi max [m.in. Turniej] nai: T(n)=2n-3; Turniej: bud n-1p,
2gi max: lg n-1. razem: T(n)=n+lgn -2
10. k-max [m.in. Hoare] [mniejsze po lew, wieksze po prawej]
 nai: T(n)=(n-1)+(n-2)+...+(n-k) =k*n - k*(k+1)/2
best: [H] T(SPLIT,n )=n-1=Θ(n)  A(n,k)=O(n) 
11. SelS [znajdz min i wstaw na pocz, znajdz min, wstaw na 2poz]
domin porow: T(n)=n-1+n-2+...+2+1=n(n-1)/2 = Θ (n2)
domin zamiana: T(n)=1*(n-1)=n-1=Θ(n) 
12. InsS [zamien od pocz wieksze z mniejszymi]
W(n)=Si=2...n(i-1)=n(n-1)/2=O(n2); A(n)=(1/4)n2 +O(n)
13. MerS dziel i zwyciężaj! W=O(n+m); MS: T(n)=Θ(n lgn)
14. QS dziel i zwycięż! [mniejsze po lewej, wieksze po prawej]
W(n)=(n-1)+W(n-1)= S i=2...n(i-1)=Θ(n2);  A(n)=Θ(n lgn)
15. Sort liniowe tworz. kosz = Θ(k), wklad. elem Θ (n)
16. CS O(k+n)
17. RS pozycyjne T(n) = O(d* n)
18. Kol Fir,In,Out,Emp; Eratos. n+n/2+n/(2*3)+...+n/(2*...*n/2)=O(n)
19. Grafy Syst. relacyjny postaci <V,E>, gdzie V jest dowolnym 
niepustym zbiorem, a E relacją binarną w V, nazywamy grafem 
zorientowanym. Drogą w grafie G=<V,E> nazywamy ciąg wierzch.
v1, v2,...vk,  taki, że (vi, v i+1) э E dla i<k.
20. Drzewo = graf niezorientowany + spójny + acykliczny, 
pre: klp, in: lkp, post: lpk

BST: „member”: A(n)=Sni=1 1/n; średni: A(n)<= k lgn, k-stała.
„minimum”: W(n)=O(n);  A(n)=O(lg n) „insert”: A(n)=O(lg n)
Worst: W(n)=n2 (elem sa uporz); Tworz: O(n lgn) [l<k<p]
AVL: różnica poziomów 0 lub 1; waga: prawy poziom-lewy
insert: max 1 rotacja, del co najwyżej tyle rotacji ile jest poziom.w drz.
Koszty min, member, insert i delete są rzędu O(lg n); sortow O(nlgn)
21. Drzewo decyzyjne W(n)=n lgn, h=lg n!, n! liści
22. Kopiec etykietowane, doskonałe drzewo binarne częściowo uporządk.
Drzewo częściowo uporz. - każdy poza jednym ma dwóch synów.
Drzewo doskonałe - wszystkie poziomy drzewa, z wyjątkiem co najwyżej 
ostatniego poziomu, są maksymalnie zapełnione, a na ostatnim poziomie 
wszystkie liście  są zgrupowane maksymalnie na lewo.
Insert/delmin=O( lg(n+1) ); O(lgn), utw O(n), W(n)=l.wierz*l.por=O(n)
sortow=utworz+n*O(lg n)=O(n lgn)
23. Kolejki priorytetowe struktura danych której uniwersum składa się z 
dwóch rozłącznych zbiorów Et i Q i określone są op.:insert,delmin,min,member,
empty.„Każdy model specyfikacji Kolejek Priorytetowych jest izomorficzny 
z pewnym modelem standardowym.”
Słowniki struktura danych której uniwersum składa się z dwóch rozłącznych
zbiorów Et i S i określone są op.: insert, delete, member, amb, empty
Najprostszy model - adresowanie bezpośrednie - ( dobry czas, dużo dziur)
Tablice mieszające [hash-table] – (kolizje)Tablica kolejek – (bez kolizji)
W tablicy hash w przypadku, gdy kolizje rozw. przez kolejki, koszt nieudanego 
poszukiwania to Θ (1+a), o ile koszt obliczenia funkcji mieszającej jest stały.
Dług. kolejki - w najgorszym razie n , czyli card (U), średnio n/m
24. Algorytmy na grafach
BFS(k)=weź pierw i dopisz, wypisz, usun pierw. DFS(s)=pop, wyp, usun, dopisz
Kruskal-suma krawędzi ma być jak najmniejsza (dowolna kolejność) O(m lgn)
Dijkistry [zachł]: najkrótsza ścieżka od a do b, od b do c... O(card(V)2); O(n2)
25. Huffman O(n lgn)
Agorytm MCM:  Koszt O(n3)
26. Trudne problemy informatyki
Hanoi: koszt: T(n)=2n-1;    Problemy decyzyjne(katy(t/n)): Koszt  (n!)
Problem komiwojażera: Alg. naiw. wygenerować wszystkie cykle: Koszt (n!)
Problem spełnialności: Koszt  2 n dla formuły o długości n
Ścieżki Hamiltona [NP.-zup nie sa znane alg wielom]: Koszt  (n!) 
Ścieżki Eulera: Koszt O(m);  Problem stopu jest nierozstrzygalny (halt) 
[nie istn alg, który dla dow danych po skoncz liczbie krokow da rozw]
problem jest wielomianowy gdy kadzy alg rozwiazujacy ten problem dla
danych o rozm n ma koszt rzedu nk, dla stalej k
-- metody konstr alg: Programowanie dynamiczne