234218 - מבני נתונים 1


complexity
winter_1415_a

תהיינה f(n),g(n):NNf(n),g(n) \colon \mathbb{N} \to \mathbb{N}פונקציות חיוביות ממש (כלומר f(n),g(n)1f(n),g(n) \geq 1 לכל nNn \in \mathbb{N}). הוכיחו שאם f(n)=O(g(n))f(n) = O(g(n))אזי קיים קבוע d>0d > 0 כך שלכל nNn \in \mathbb{N} מתקיים: f(n)dg(n)f(n) \leq d\cdot g(n).

Feedback