Question

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).

0

Answers

נתון לנו כי f(n)=O(g(n))f(n) = O(g(n))כלומר קיים קבוע cc כך שלכל nNn\in \mathbb{N} החל מ - n0n_0 מסוים מתקיים f(n)cg(n)f(n) \leq c\cdot g(n).

נסמן

d=max{f(n)nn0}, d' = \max\{f(n) \mid n \leq n_0\},

ונבחר את dd להיות

d=max{c,d}. d = \max\{c,d'\}.

נראה כי עבור dd זה הטענה מתקיימת. עבור n>n0n > n_0 הטענה בבירור מתקיימת כיוון ש cdc\leq d ולכן

f(n)cg(n)dg(n), f(n) \leq c\cdot g(n) \leq d\cdot g(n),

כנדרש.

עבור nn0n \leq n_0מתקיים f(n)df(n) \leq d' מההגדרה של dd' ולכן, f(n)df(n) \leq d, כעת נשתמש בכך שg(n)1g(n) \geq 1 ונקבל

f(n)ddg(n) f(n) \leq d \leq d\cdot g(n)

כנדרש, לכל nNn \in \mathbb{N}.

0
Feedback