Skip to content

3-6 Variations on OO and Ω\Omega

Some authors define Ω\Omega-notation in a slightly different way than this textbook does. We'll use the nomenclature Ω∞\stackrel{\infty}{\Omega} (read "omega infinity") for this alternative definition. We say that f(n) = Ω∞(g(n))\stackrel{\infty}{\Omega}(g(n))if there exists a positive constant cc such that f(n)≥cg(n)≥0f(n) \geq cg(n) \geq 0 for infinitely many integers n.

a. Show that for any two asymptotically nonnegative functions f(n)f(n) and g(n)g(n), we have f(n)=O(g(n))f(n)=O(g(n)) or f(n)=Ω∞(g(n))f(n)=\stackrel{\infty}{\Omega}(g(n)) (or both).

b. Show that there exist two asymptotically nonnegative functions f(n)f(n) and g(n)g(n) for which neither f(n)=O(g(n))f(n) = O(g(n)) nor f(n)=Ω(g(n))f(n) = \Omega(g(n)) holds.

c. Describe the potential advantages and disadvantages of using Ω∞\stackrel{\infty}{\Omega}-notation instead of Ω\Omega-notation to characterize the running times of programs.

Some authors also define OO in a slightly different manner. We’ll use O′O' for the alternative definition: f(n)=O′(g(n))f(n)=O'(g(n)) if and only if ∣f(n)∣=O(g(n))|f(n)|=O(g(n)).

d. What happens to each direction of the "if and only if" in Theorem 3.1 on page 56 if we substitute O′O' for OO but still use Ω\Omega?

Some authors define O~\tilde{O}(read "soft-oh") to mean O with logarithmic factors ignored:

O~(g(n))={f(n): there exist positive constants c,k, and n0 such that 0≤f(n)≤cg(n)lg⁡k(n) for all n≥n0}. \begin{aligned} \tilde{O}(g(n))=\lbrace f(n) : & \text{ there exist positive constants }c, k, \text{ and } n_0 \text{ such that }\cr & 0\leq f(n)\leq cg(n)\lg^k(n) \text{ for all } n\geq n_0\rbrace .\cr \end{aligned}

e. Define Ω~\tilde{\Omega} and Θ~\tilde{\Theta} in a similar manner. Prove the corresponding analog to Theorem 3.1.

a

if f(n)≠O(g(n))there must be infinite integers that f(n)≥cg(n)≥0otherwise choose the last n= that f(n)≥cg(n) as n0for all n≥n0,f(n)≤cg(n)  ⟹  f(n)=O(g(n)) \begin{aligned} \text{if } f(n)\neq O(g(n))\cr \text{there must be infinite integers that }f(n) \geq cg(n)\geq 0\cr \text{otherwise choose the last } n = \text{ that } f(n)\geq cg(n) \text{ as } n_0\cr \text{for all }n\geq n_0,f(n)\leq cg(n)\implies f(n)=O(g(n))\cr \end{aligned}

b

f(n)=n∣sin⁡n∣,g(n)=1f(n)=n|\sin n|,g(n)=1

c

  • advantages: By a we can know that OO and Ω∞\stackrel{\infty}{\Omega} can characterize relationship between any two function.
  • disadvantages: Not precise.

d

∀f(n),g(n):f(n)=Θ(g(n))  ⟹  f(n)=Ω(g(n))&f(n)=O′(g(n))but the conversion is not true \begin{aligned} \forall f(n) , g(n):\cr f(n)=\Theta(g(n)) \implies f(n)=\Omega(g(n)) \And f(n)=O'(g(n))\cr \text{but the conversion is not true} \end{aligned}

e

Ω~(g(n))={f(n): there exist positive constants c,k, and n0 such that0≤f(n)≤cg(n)lg⁡k(n) for all n≥n0}.Θ~(g(n))={f(n): there exist positive constants c1,c2,k, and n0 such that0≤c1g(n)lg⁡k(n)≤f(n)≤c2g(n)lg⁡k(n) for all n≥n0}.according to there definity: f(n)=Θ~(g(n))  ⟺  f(n)=O~(g(n))&f(n)=Ω~(g(n)) \begin{aligned} \tilde\Omega(g(n))=\lbrace f(n): & \text{ there exist positive constants }c,k,\text{ and } n_0 \text{ such that}\cr & 0\leq f(n) \leq cg(n)\lg^{k}(n) \text{ for all }n \geq n_0\rbrace .\cr \tilde\Theta(g(n))=\lbrace f(n): & \text{ there exist positive constants }c_1,c_2,k,\text{ and } n_0 \text{ such that}\cr & 0\leq c_1g(n)\lg^{k}(n)\leq f(n) \leq c_2g(n)\lg^{k}(n) \text{ for all }n \geq n_0\rbrace .\cr \text{according to there definity: } & f(n)=\tilde\Theta(g(n))\iff f(n)=\tilde O(g(n)) \And f(n)=\tilde\Omega (g(n))\cr \end{aligned}