משתמש:Ddd/mvn1

2א:לא נכון- שתי פונקציות לדוגמא:g(n)=n^2, ואם $f(n-1)<n\,$ אז f(n)=n^3 אחרת $f(n)=f(n-1)\,$נוכיח ש. $f(n)\neq O(g(n))\,$:לכל c,ולכל $\,n_{0}$ שנבחר, קיים $\,n>n_{0}$ בו $n^{3}>c\cdot n^{2}\,$כי לכל n^3 תמיד יהיה n שיהיה גדול ממנו, ואז n^3 של ה n הזה יהיה גדול מספיק. נוכיח ש $f(n)\neq \Omega (g(n))\,$:ב"מרווחים" בין הקפיצה ל n^3 עד ש f(n-1)<n הפונקציה שווה לקבוע כאשר לכל n יהיו אינסוף מרווחים עם n גדול יותר. כאשר ב "קצה" המרווח f(n)=n וזה בוודאי לא באומגה של g(n)=n^2

ב:נכון-נניח שלא מתקיים $\Omega _{\infty }$כלומר מס' הנקודות הוא סופי לכל с. לכן קיימת הנקודה שבה n הוא הגדול ביותר מבין הנקודות. נקרא לה $n_{1}\,$ הנקודה הנ"ל תלויה ב с.נבחר C מסוים $C_{0}\,$. עבורו לכל $n>n_{1}\,$מתקיים:$f(n)<c_{0}\cdot g(n)\,$ וזה מקיים לפי ההגדרה את $f(n)=O(g(n))\,$

ג:נכון- צריך להוכיח:עבור כל c>0 קיים $n_{0}\,$ כך שעבור כל $n>n_{0}\,$ מתקיים $n^{\epsilon }\geq c\cdot log^{k}(n)$הזזת אגפים:${\frac {n^{\epsilon }}{log^{k}(n)}}\geq c$ אבל ידוע שלכל a,b>0 $lim_{x\rightarrow \infty }{\frac {x^{a}}{ln^{b}(x)}}=0$ לכן, ע"פ הגדרת הגבול, לכל קבוע C קיים n>0 כך שהתנאי מתקיים. מש"ל

ד.נכון-הפונקציה $f(x)={\frac {1}{x}}$ ע"פ ההגדרה קיים C=1 ו $n_{0}=1\,$ ואכן, בתחום הזה ${\frac {1}{sqrt(x)}}\geq {\frac {1}{x}}$

ה.לא נכון-נניח בשלילה שזה נכון,$log*(log(n))=log*(n)-1\,$לפי ההגדרה(כי צריך לעשות לוג פעם אחת פחות. צריך להוכיח: קיימים $\,C,n_{0}$ כך ש $log^{*}(n)-1\leq c\cdot log(log^{*}(n))$העברת אגפים:${\frac {log^{*}(n)}{log(log^{*}(n))}}-{\frac {1}{log(log^{*}(n))}}\leq c$ אבל כאשר n שואף לאינסוף, החלק הראשון בביטוי השמאלי שואף לאינסוף(ע"פ הגבול בסעיף ג) והחלק השני שואף לאפס כי המכנה שואף לאינסוף. לכן זה יהיה גדול מכל קבוע, ולכן זה לא נכון.

ו.לא נכון-ע"פ נוסחת סטירלינג, $log(n!)\cong nlog(n)-n$ בנוסף $[log(n)]!=e^{log([log(n)]!)}\cong e^{log(n)\cdot log(log(n))-log(n)}={\frac {n^{log(logn)}}{n}}$ המשך הפיתוח: $n^{log(logn)-1}\,$ומכיוון שקיים n עבורו $log(log(n))-1>2\,$ זה לא יכול להיות ב $O(nlog(n)-n)\,$ כי חזקת n גדולה יותר.

ז.נכון-כפי שהראיתי, ב$[log(n)]!\,$ (מעבר ל n מסוים) חזקת n גדולה מאשר ב log(n!) ולכן ע"פ ההגדרה (אם נבחר למשל כ $\,n_{0}$ אם המספר שעבורו $log(log(n))-1\geq 2$ אז מכיוון ש $nlog(n)=log(n^{n})\geq log(n!)$ מתקיים:$n^{log(log(n))-1}\geq nlog(n)\geq log(n!)$

ח.לא נכון-ע"פ ההגדרה, לכל C קיים $\,n_{0}$ כך שעבור כל $\,n>n_{0}$ מתקיים $1\leq c\cdot f(n)$. ע"פ הטענה $(f(n))^{2}=O(f(n))\,$כלומר קיימים $\,c_{1},n_{1}$ כך שעבור כל $\,n>n_{1}$ מתקיים $(f(n))^{2}\leq c_{1}f(n)$אבל אם נבחר $\,c_{2}>c_{1}$ ע"פ הנתון קיים $\,n_{0}$ שלכל n גדול ממנו $f(n)\geq c_{2}$ואם נכפול את שני הצדדים ב f(n) נקבל $(f(n))^{2}\geq c_{2}f(n)>c_{1}f(n)$ וזה סותר את הטענה, ולכן היא לא נכונה