מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה/תרגילים/שאלה בסיסית ביחסים/תשובה

1

נכון.

הוכחה: נבחר $\displaystyle c=1$‏ ו$\displaystyle n_{0}=100$‏,‏ ונוודא $\displaystyle \forall _{n\geq 100}80\leq 1\cdot 3\cdot n$.

2

נכון.

הוכחה: נבחר $\displaystyle c=2^{1008}$‏ ו$\displaystyle n_{0}=1$‏,‏ ונוודא $\displaystyle \forall _{n\geq 1}2^{n+1003}+30=2^{1003}\cdot 2^{n}+30\leq 2^{1008}\cdot 2^{n}$.

3

נכון.

הוכחה: נבחר $\displaystyle c=3$‏ ו$\displaystyle n_{0}=1$‏,‏ ונוודא $\displaystyle \forall _{n\geq 1}2\cdot n+7\leq 3\cdot (2\cdot n+3)=6\cdot n+9$.

4

לא נכון.

הוכחה: נניח בשלילה שהטענה נכונה, ולכן עבור $\displaystyle c>0$ ו$\displaystyle n_{0}>0$ כלשהם, $\displaystyle \forall _{n\geq n_{0}}3\cdot n\leq c\cdot 1$. אם נציב $\displaystyle n=n_{0}+\left\lceil c\right\rceil ,$ נקבל

$\displaystyle (3\cdot n)|^{n_{0}+\left\lceil c\right\rceil }=3\cdot n_{0}+3\cdot \left\lceil c\right\rceil \leq$
$\displaystyle (c\cdot 1)|^{n_{0}+\left\lceil c\right\rceil }=c,$
שאינו הגיוני.

5

נכון.

הוכחה: באופן כללי, $\displaystyle \log _{b}(a)=\log _{c}(a)/\log _{c}(b)$, ולכן הביטויים הם למעשה אותו ביטוי עד כדי הכפלה בקבוע.