the Big-O notation problems

**narbe** · September 18th 2008, 10:36 PM

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

**Laurent** · September 19th 2008, 07:30 AM

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).

**CaptainBlack** · September 20th 2008, 01:06 AM

Originally Posted by Laurent

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

**CaptainBlack** · September 20th 2008, 01:12 AM

Originally Posted by narbe

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

**narbe** · September 20th 2008, 05:26 AM

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

**bkarpuz** · September 20th 2008, 07:45 AM

Originally Posted by narbe

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

Thread: the Big-O notation problems

LinkBack

Thread Tools

Display

the Big-O notation problems

7 new problems

Landau symbol

Similar Math Help Forum Discussions

Notation problems

matrix sigma notation problems

how to convert problems into scientifc notation?

Absolute Value Notation/Inequality and Interval Notation

sets and set notation 3 problems

Search Tags