טוב זו הפונקציה הלא מסובכת:
וזה הניתוח שלי:
לולאת ה for הפנימית מתבצעת
\frac{n}{\sqrt{i}}
פעמים (שניהם לא משתנים במהלך הלולאה),
הלולאה החיצונית רצה מ i=1 עד i=n
לכן סה"כ יש:
T(n)=\sum_{i=1}^{n}\cdot O\left(\frac{n}{\sqrt{i}}\right)=O\left(n\cdot\sum_{i=1}^{n}\frac{1}{\sqrt{i}}\right)=
איך אני נפטר מהסכום הזה? אפשר לחסום אותו ע"י n אבל זה נראה לי גדול מידי.
