1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Big O Notation Proofs

  1. Sep 12, 2009 #1
    O-notation
    – O(g(n)) = { f (n) : there exist positive constants c and n0 such that
    0 ≤ f (n) ≤ cg(n) for all n ≥ n0}
    – g(n) is an upper bound of f(n), may not be tight

    Ω-notation
    – Ω(g(n)) = { f (n) : there exist positive constants c and n0such that
    0 ≤ cg(n) ≤ f(n) for all n ≥ n0}
    – g(n) is an lower bound of f(n), may not be tight Θ-notation

    – Θ(g(n)) = { f (n) : there exist positive constants c1, c2, and n0such
    that 0 ≤ c1g(n) ≤ f (n) ≤ c2 g(n) for all n ≥ n0}
    – We write f (n) = Θ(g(n)) instead of f (n) ∈Θ(g(n))
    – g(n) is an asymptotically tight bound for f(n)

    1) [tex]n^{2} + 2n^{3} = O(n^{3}) [/tex]
    [tex]f(n) = 2n^{3}, g(n)= (n^{3}) [/tex]
    if [tex]f(n) \in O(g(n))[/tex]
    [tex]0 \leq f(n) \leq cg(n)[/tex]
    [tex]0 \leq 2n^{3} \leq c*n^{3} for \ n \geq 0[/tex]
    [tex]any \ c \geq 2 \ \ f(n) \leq g(n) \ for \ n \geq 0[/tex]

    2)[tex]2n + n^{2} \neq \Omega (n^{3}) [/tex]
    [tex]f(n)=n^{2}, g^{3}[/tex]
    [tex]0 \leq cg(n) \leq f(n)[/tex]
    [tex]0 \leq c*n^{3} \leq n^{2} \ for \ n \geq 0[/tex]
    [tex]any \ c \leq \frac{1}{n} \ for \ n \geq 0 [/tex]

    3) [tex]ln \ n = \Theta (lg \ n) [/tex]
    f(n) = Θ(g(n))
    C1lg(n) ≤ ln(n) ≤ C2lg(n)
    (1)ln(n) ≤ C2lg(n)
    C2 = 1
    ln(n) ≤ lg(n)
    n = 1
    e^x = 1 n^x = 1
    x = 0
    holds for all n > 0


    (2)C1lg(n) ≤ ln(n)
    C1 = ½
    ½lg(n) ≤ ln(n)
    n = 1
    ½(0) ≤ 0
    holds for all n > n/2

    I am a beginner and looking for feedback. Are there any mistakes I have made or changes that need to be made when proving these?
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?



Similar Discussions: Big O Notation Proofs
Loading...