Results 1 to 3 of 3

Math Help - Properly Solving a Big O Proof

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    1

    Properly Solving a Big O Proof

    Hello,

    I am currently taking a class which is covering a topic which I have not yet had experience with. I have done a lot of research on the topic, and believe to understand the definition well, however, I'm not sure how to go about truly applying the definition.

    I will type up the question below with modified numbers so I can see how to really solve the problem rather than simply receiving the answer.

    The questions are as follow:

    Code:
    Indicate for each of the following pairs of expressions (A,B) whether A is O, Ω, Θ of B.
    
    (1) 
    
    
    
    
    5^{\log_{5}(n)} and 
    
    
    
    
    3n+2
    (2) 
    
    
    
    
    n^2 and 
    
    
    
    
    (\sqrt{3})^{\log(n)}}
    So for the first one I get to a point similar to this:

    Code:
    
    
    
    
    
    5^{\log_{5}(n)} = n
    so new question:
    
    
    
    
    
    n is 
    
    
    
    
    O(3n+2)
    But I'm not sure how to draw the proof from here. I understand that Big O is the upper-bound of a function and to prove it, some numbers c and k (k is the same as n_0) must make this statement true (where f(x) = original and g(x) = bound equation):

    Code:
    
    
    
    
    
    f(x) \le c*g(x) for every number 
    
    
    
    
     x \ge k
    My biggest issue is finding my numbers c and k. Are these arbitrary values which make the statement true or is there a better way to find them?

    As for the second set of numbers, I'm just not exactly sure where to begin. Again, I have changed the numbers so there are not my homework problems, but do highly resemble them. So I appreciate concept explanations over answers - the answers are irrelevant if I don't understand the concept.

    Thank you for your help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2009
    From
    1111
    Posts
    872
    Thanks
    3
    Quote Originally Posted by RageD View Post
    Hello,

    I am currently taking a class which is covering a topic which I have not yet had experience with. I have done a lot of research on the topic, and believe to understand the definition well, however, I'm not sure how to go about truly applying the definition.

    I will type up the question below with modified numbers so I can see how to really solve the problem rather than simply receiving the answer.

    The questions are as follow:

    Code:
    Indicate for each of the following pairs of expressions (A,B) whether A is O, Ω, Θ of B.
    
    (1) 
    
    
    
    
    5^{\log_{5}(n)} and 
    
    
    
    
    3n+2
    (2) 
    
    
    
    
    n^2 and 
    
    
    
    
    (\sqrt{3})^{\log(n)}}
    So for the first one I get to a point similar to this:

    Code:
    
    
    
    
    
    5^{\log_{5}(n)} = n
    so new question:
    
    
    
    
    
    n is 
    
    
    
    
    O(3n+2)
    But I'm not sure how to draw the proof from here. I understand that Big O is the upper-bound of a function and to prove it, some numbers c and k (k is the same as n_0) must make this statement true (where f(x) = original and g(x) = bound equation):

    Code:
    
    
    
    
    
    f(x) \le c*g(x) for every number 
    
    
    
    
     x \ge k
    My biggest issue is finding my numbers c and k. Are these arbitrary values which make the statement true or is there a better way to find them?

    As for the second set of numbers, I'm just not exactly sure where to begin. Again, I have changed the numbers so there are not my homework problems, but do highly resemble them. So I appreciate concept explanations over answers - the answers are irrelevant if I don't understand the concept.

    Thank you for your help!
    Dear RageD,

    5^{\log_{5}(n)} = n~\forall ~n~\geq{0}

    Therefore, 5^{\log_{5}(n)}\leq{3n}<3n+2~\forall ~n~\geq{0}

    5^{\log_{5}(n)}<3n+2~\forall ~n~ \geq{0}

    As you can see, k=0 and c=1 in this case.

    Hence, n=5^{\log_{5}(n)}\in{O(3n+2)}

    Hope you understood.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    My biggest issue is finding my numbers c and k. Are these arbitrary values which make the statement true or is there a better way to find them?
    The answer is, yes and yes. To have a proof that f(x) is O(g(x)) is it sufficient to find any c and k at all as long as |f(x)| <= c * |g(x)| for x >= k. But there are standard ways to find upper and lower bounds of functions. For example, it is typical to use the fact that c_nx^n+\dots+c_1x+c_0\le x^n(c_n+\dots+c_1+c_0) for x\ge 1.

    For the second problem, assuming logarithm is to the base 2, \sqrt{3}^{\log n}=(2^{\log\sqrt{3}})^{\log n}=(2^{\log n})^{\log\sqrt{3}}=n^{(\log 3)/2}. Since \log_2 3<\log_24=2, n^2/(n^{(\log 3)/2})=n^{2-(\log 3)/2} becomes greater than any particular constant c. Therefore, n^2 cannot be less than cn^{(\log 3)/2} from some n on.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: February 9th 2011, 04:35 AM
  2. Is map defined properly?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: June 30th 2010, 04:04 AM
  3. is this integrer solved properly?
    Posted in the Calculus Forum
    Replies: 2
    Last Post: May 28th 2009, 01:24 PM
  4. Did I integrate these properly?
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 14th 2009, 06:41 AM
  5. Properly Divergent Limits
    Posted in the Calculus Forum
    Replies: 1
    Last Post: September 25th 2008, 02:26 PM

Search Tags


/mathhelpforum @mathhelpforum