Results 1 to 5 of 5

Math Help - proving

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    3

    proving

    Can someone please explain this to me?


    Given f(n)=2n + 3 lg n, g(n)=n, prove that 2n + 3 lg n = Θ(n)

    Proof:
    2n + 3 lg n ≤ 2n+3n = 5n for all n ≥ 1
    Hence, we can take k1 =5, and n1=1, and conclude that f(n)= O(n)
    Since 2n + 3 lg n ≥ 2n, for all n ≥ 1,
    we can take k2 = 2, and n2=1, and conclude that f(n) = Ω(n)
    Therefore, we have 2n + 3 lg n = Θ(n)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    Posts
    461
    Hello

    Quote Originally Posted by dandeliondream View Post
    Can someone please explain this to me?


    Given f(n)=2n + 3 lg n, g(n)=n, prove that 2n + 3 lg n = Θ(n)

    Proof:
    2n + 3 lg n ≤ 2n+3n = 5n for all n ≥ 1



    2n + 3 lg(n) \le 2n +3n = 5n, because lg(n) \le n,\ n \ge 1

    Quote Originally Posted by dandeliondream View Post
    Hence, we can take k1 =5, and n1=1, and conclude that f(n)= O(n)
    You showed that f(n) = 2n + 3 lg(n) \le 5n

    5n is in O(n), so f(n) is in O(n)

    10312381n would be in O(n), too


    Quote Originally Posted by dandeliondream View Post
    Since 2n + 3 lg n ≥ 2n, for all n ≥ 1,
    ln(n) \ge 0
    Quote Originally Posted by dandeliondream View Post
    we can take k2 = 2, and n2=1, and conclude that f(n) = Ω(n)
    pretty obvious, because 2n is in Ω(n) and so is f(n)

    Quote Originally Posted by dandeliondream View Post
    Therefore, we have 2n + 3 lg n = Θ(n)
    Quote Originally Posted by dandeliondream View Post
    Because f(n) is in O(n) and Ω(n)

    Rapha
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    Posts
    3
    Quote Originally Posted by Rapha View Post
    Hello


    2n + 3 lg(n) \le 2n +3n = 5n, because lg(n) \le n,\ n \ge 1
    How do I know above is = 5n?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2008
    Posts
    461
    Quote Originally Posted by dandeliondream View Post
    How do I know above is = 5n?
    Do you know that  lg(n) \le n \ \forall n \ge 1 ?

    That's all you need to know, because

    2n +3\cdot \displaystyle{\underbrace{lg (n)}_{\displaystyle{\le n}}}  \le 2n +3\cdot n = 5n

    In the next line

    2n + 3 lg n ≥ 2n

    it is the same argument

    lg (n) \ge 0 \forall n \ge 1


    So 2n + 3 \displaystyle{\underbrace{lg (n)}_{\displaystyle{\ge 0}}} \ge 2n +0
    Last edited by Rapha; April 11th 2010 at 01:57 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2010
    Posts
    3
    Quote Originally Posted by Rapha View Post
    Do you know that  lg(n) \le n \ \forall n \ge 1 ?

    That's all you need to know, because

    2n +3\cdot \displaystyle{\underbrace{lg (n)}_{\displaystyle{\le n}}} \le 2n +3\cdot n = 5n
    Thank you for taking time to explain to me.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving y^2=-4x
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: May 27th 2010, 08:48 AM
  2. Proving CRT
    Posted in the Advanced Algebra Forum
    Replies: 11
    Last Post: April 13th 2010, 11:14 PM
  3. Please me proving this.
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: March 28th 2010, 12:29 AM
  4. Proving an identity that's proving to be complex
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: July 21st 2009, 02:30 PM
  5. Proving
    Posted in the Trigonometry Forum
    Replies: 4
    Last Post: March 27th 2008, 09:27 PM

Search Tags


/mathhelpforum @mathhelpforum