###### tags: `Matematyka Dyskretna M`

# Lista 1

## 1
a) $a_n = \frac{2n^{81,2} + 3n^{45,1}}{4n^{23,3} + 5n^{11,6}} = \frac{2n^{57.9} + 3n^{21.8}}{4 + \frac{5}{n^{11.7}}} = O(n^{57.9})$, czyli k = 57.9

b) $a_n = 5^{log_2n} = 2^{log_2nlog_25} = n^{log_25} = O(n^{log_25})$, czyli k = $log_25$

c) $a_n = (1,001^n)$ Z definicji notacji dużego O

$\lim\limits_{n \to \infty} \frac{1,001^n}{n^k} < \infty$

$\lim\limits_{n \to \infty} \frac{1,001^n}{n^k} = \lim\limits_{n \to \infty}
e^{ln\frac{1,001^n}{n^k}} = e^{\lim\limits_{n \to \infty}ln\frac{1,001^n}{n^k}} = e^{\lim\limits_{n \to \infty}ln1,001^n - lnn^k} = e^{\lim\limits_{n \to \infty}n(ln1,001 - \frac{k*lnn}{n})} = +\infty$ Czyli nie istnieje takie k $\in \mathbb{N}$, bo niezależnie od wyboru k, $\frac{1,001^n}{n^k}$ dąży do $+\infty$

d)
$a_n = n*log^3n$
$\lim\limits_{n \to \infty} \frac{n*log^3n}{n^k} < \infty$
$\lim\limits_{n \to \infty} \frac{n*log^3n}{n^k} = \lim\limits_{n \to \infty} \frac{log^3n}{n^{k-1}}\stackrel{\mbox{l`H}}{=}\lim\limits_{n \to \infty}\frac{\frac{3log^2n}{n}}{(k-1)*n^{k-2}} =\lim\limits_{n \to \infty}\frac{3log^2n}{(k-1)*n^{k-1}} \stackrel{\mbox{l`H}}{=}\lim\limits_{n \to \infty}\frac{\frac{6logn}{n}}{(k-1)^2*n^{k-2}} =\lim\limits_{n \to \infty} \frac{6logn}{(k-1)^2*n^{k-1}}\stackrel{\mbox{l`H}}{=}\lim\limits_{n \to \infty}\frac{6}{(k-1)^3*n^{k-1}} =\frac{6}{(k-1)^3}*\lim\limits_{n \to \infty} \frac{1}{n^{k-1}}$

Czyli $\forall_{k>1}$ $\lim\limits_{n \to \infty} \frac{n*log^3n}{n^k} < \infty$
Czyli nie istnieje najmniejsze k takie, że $a_n= O(n^k)$

## 2

1. $0,99^n$ - funkcja malejąca
2. $(1 + \frac{1}{n})^n$ - dąży do e
3. $log{n}$ - logarytm wolniej dąży do $\infty$ niż n
4. n - wolniej dąży niż $logn^n$, bo $logn^n$ = $nlogn$
5. $logn^n$ - rośnie wolnej niż $3^{logn}$, ponieważ $3^{logn}$ = $(2^{log_23})^{logn} = 2^{log_23*logn} = n^{log_23}$, a potęgowa funkcja rośnie szybciej niż $nlogn$
6. $3^{logn}$ - rośnie wolnej niż $n^2$, bo $3^{logn}= n^{log_23}$, a $log_23 < 2$
7. $n^2$ - rośnie wolniej niż $n^{logn}$, bo $n^2$ = $2^{2log_2n}$, a $n^{logn}$ = $2^{log_2n * logn}$ = $2^{log^2_2n}$
8. $n^{logn}$ - rośnie wolniej niż $2^{\sqrt{n}}$, bo $n^{logn}$ = $2^{log^2_2n}$, a $logarytm^2$ rośnie wolniej niż $\sqrt{n}$
9. $2^{\sqrt{n}}$- rośnie wolniej niż $1,01^n$, bo $1,01^n$ = $2^{nlog_21,01}$
10. $1,01^n$ - rośnie wolniej niż $(logn)^n$, bo $(logn)^n$ = $2^{nlog_2(log_2n)}$, a z podpunktu 9 $1,01^n$ = $2^{nlog_21,01}$
11. $(logn)^n$ - rośnie najszybciej

## 6

$e^{\frac{1}{n}} = \displaystyle\sum_{i=0}^{\infty} \frac{\frac{1}{n^i}}{i!} = 1 + \frac{1}{n} + \displaystyle\sum_{i=2}^{\infty}\frac{1}{n^i*i!} \leq 1 + \frac{1}{n} + \frac{1}{n^2}\displaystyle\sum_{i=2}^{\infty}\frac{1}{i!} \leq 1 + \frac{1}{n} + \frac{1}{n^2}\displaystyle\sum_{i=2}^{\infty}\frac{1}{2^i} \leq 1 + \frac{1}{n} + \frac{1}{n^2}*\frac{1}{2} < 1 + \frac{1}{n} + \frac{1}{n^2} = 1 + \frac{1}{n} + O(\frac{1}{n^2})$

Podczas rozwiązywania tego zadania korzystałem z faktu, $f(x)<=g(x)$ oraz $g(x) = O(\frac{1}{n^2}) \Rightarrow f(x) = O(\frac{1}{n^2})$

## 7

Zakładamy, że znalezenie minimum z ciągu n-elementowego zajmuje n instrukcji.

Wybieramy najmniejszy element w n instrukcji, kolejny w n-1 instrukcji ... ostatni w 1 instrukcje.
**Ilość instrukcji** $= n + (n-1) + (n-2) + ... + (1) = \frac{n*(n+1)}{2} < 1 * n^2$, czyli algorytm działa w czasie $O(n^2)$

## 8

\begin{equation}
\frac{
\begin{array}[b]{r}
\left( x_1 x_2 ... x_n\right)\\
+ \left( x'_1 x'_2 ... x'_n\right)
\end{array}
}{
\left(y_1 y_2 ... y_n\right)
}
\end{equation}

W najgorszym przypadku będziemy musieli dodać n cyfr do n cyfr i dodatkowo dodać ewentualne "przeniesienia" cyfry jeden w przypadku gdy wynik wyjdzie nam >9. Wtedy wykonamy n + (n-1) operacji dodawania i jedno przepisanie liczby na samym końcu, co daje dam 2n operacji czyli czasowo jest to $O(n)$

\begin{equation}
\frac{
\begin{array}[b]{r}
\left( x_1 x_2 ... x_n\right)\\
\times \left( x'_1 x'_2 ... x'_n\right)
\end{array}
}{
\left(y_{11} y_{12} ... y_{1n}\right)\\
\left(y_{21} y_{22} ... y_{2n}\right)\\
\left(...\right)\\
+\left(y_{n1} y_{n2} ... y_{nn}\right)
}
\end{equation}

W przypadku mnożenia musimy dodać n przeniesień, wymnożyć n razy cyfry, oraz wykonać operacje dodawania n razy n - długości liczb. Czyli $T(n) = n + n + n * n = n^2 + 2n = O(n^2)$

## 10

Policzmy całkę nieoznaczoną $\int\frac{1}{x}\mathrm{d}x = lnx$
oraz $\int\frac{1}{x + 1}\mathrm{d}x = ln(x + 1)$

Pierwsza całka ogranicza nam sumę z góry, druga - z dołu
$\int_0^n \frac{1}{x + 1}\mathrm{d}x = ln(n + 1) - ln(1) = ln(n + 1) \leq \displaystyle\sum_{k=1}^n \frac{1}{k} =1 + \displaystyle\sum_{k=2}^n \frac{1}{k} \leq 1 + \int_1^n \frac{1}{x}\mathrm{d}x = 1 + ln(n) - ln1 = 1 + ln(n)$

## 14

Teza: $\lfloor{\sqrt{x}}\rfloor = \lfloor{\sqrt{\lfloor{x}\rfloor}}\rfloor$

Z własności podłogi: Jeżeli $\lfloor\sqrt{\lfloor{x}\rfloor}\rfloor = n$ to

$n <= \sqrt{\lfloor{x}\rfloor} < n+1$ / $\uparrow^2$ (strony nierówności są dodatnie)

$n^2 <= \lfloor{x}\rfloor < (n + 1)^2$ (x >=0, więc moduł z liczby zwraca nią samą)

($n \in \mathbb{N} \Rightarrow n^2 \in \mathbb{N}$ oraz $n+1 \in \mathbb{N} \Rightarrow (n+1)^2 \in \mathbb{N}$)

Korzystając z tego, że jeśli $z \in \mathbb{N}$ to z <= $\lfloor{y}\rfloor < z + 1 \Leftrightarrow z <= y < z + 1$

$n^2 <= x < (n + 1)^2$ / $\sqrt{}$ (wszystkie strony są dodatnie więc domyślnie wartość bezwzględna jest zdjęta)
$n <= \sqrt{x} < n + 1$

Z własności podłogi

n = $\lfloor\sqrt{x}\rfloor$

czyli n = $\lfloor\sqrt{\lfloor{x}\rfloor}\rfloor = \lfloor\sqrt{x}\rfloor$
$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\blacksquare$