Results 1 to 6 of 6

Math Help - the Big-O notation problems

  1. #1
    Banned
    Joined
    Sep 2008
    Posts
    21

    Cool the Big-O notation problems

    hello folks.
    Can you help me solve these problems of big O notation and moreover, can you explain for me the easiest way to solve Big O notation problems? I mean, how do we begin to solve and what is the general concept?
    Thanks in advance
    Attached Thumbnails Attached Thumbnails the Big-O notation problems-gash.jpg  
    Last edited by CaptainBlack; September 20th 2008 at 02:04 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    The question in your textbook is not quite rigorously written: it is necessary to specify at the neighbourhood of which point you define the big-O notation. For instance, it seems clear in the present case that it should be \underset{x\to\infty}{O}(x^n).

    That said, f(x)=\underset{x\to\infty}{O}(x^n) means no more than |f(x)|\leq C x^n for some C and for large enough x. I'll neglect the subscript under the O in the following (but write it on your paper anyway!).

    Because O(x^n)+O(x^n)=O(x^n), what you have to do is only to look at the largest term (when x tends to +\infty). You determine which one is larger by using usual comparisons between polynomial terms, and between polynomial and logarithmic terms. For instance, for a), the dominating term is x^3\log x (it is larger than x^3, which dominates x^2). This term is not O(x^3) because x^3\log x \leq Cx^3 is not compatible with \log x\to+\infty. On the other hand \log x=O(x), so that x^3\log x=O(x^4). As a summary, 2x^2+x^3\log x=O(x^2)+x^3 O(x)=O(x^2)+O(x^4)=O(x^4) and it is not O(x^3) since x^{-3}(2x^2+x^3\log x)=2x^{-1}+\log x\to +\infty.

    For b), remember (\log x)^4=O(x).
    For c), you can use \frac{1}{x^4+1}=O(x^{-4}) (or look at the limit as x tends to +\infty).
    For d), cf. a) and c).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Laurent View Post
    The question in your textbook is not quite rigorously written: it is necessary to specify at the neighbourhood of which point you define the big-O notation. For instance, it seems clear in the present case that it should be \underset{x\to\infty}{O}(x^n).
    There is no need for the x \to \infty notation it is implicit in the usual definition of Big-O notation.

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by narbe View Post
    hello folks.
    Can you help me solve these problems of big O notation and moreover, can you explain for me the easiest way to solve Big O notation problems? I mean, how do we begin to solve and what is the general concept?
    Thanks in advance
    For a description of Big-O notation see the Wikipedia article.


    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Sep 2008
    Posts
    21

    Exclamation 7 new problems

    Hello my friends,
    I added 7 new problems regarding Big-O notation. I need to know, how you solve them. I want to learn the way and the logic to solve them. Thank you for helping me
    Attached Thumbnails Attached Thumbnails the Big-O notation problems-6.jpg   the Big-O notation problems-10.jpg   the Big-O notation problems-12-14-16.jpg   the Big-O notation problems-18.jpg   the Big-O notation problems-24.jpg  

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2

    Exclamation Landau symbol

    Quote Originally Posted by narbe View Post
    hello folks.
    Can you help me solve these problems of big O notation and moreover, can you explain for me the easiest way to solve Big O notation problems? I mean, how do we begin to solve and what is the general concept?
    Thanks in advance
    The link below illustrates the Landau symbols O(big-o) and o(small-o), I think it will be helpful
    Landau Symbols -- from Wolfram MathWorld
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Notation problems
    Posted in the Calculus Forum
    Replies: 5
    Last Post: August 2nd 2011, 01:28 AM
  2. matrix sigma notation problems
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 29th 2010, 01:56 AM
  3. Replies: 2
    Last Post: November 10th 2009, 09:00 PM
  4. Replies: 1
    Last Post: August 26th 2009, 01:40 PM
  5. sets and set notation 3 problems
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 3rd 2006, 12:19 PM

Search Tags


/mathhelpforum @mathhelpforum