# Thread: the Big-O notation problems

1. ## 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?

2. 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 $\displaystyle \underset{x\to\infty}{O}(x^n)$.

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

Because $\displaystyle O(x^n)+O(x^n)=O(x^n)$, what you have to do is only to look at the largest term (when $\displaystyle x$ tends to $\displaystyle +\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 $\displaystyle x^3\log x$ (it is larger than $\displaystyle x^3$, which dominates $\displaystyle x^2$). This term is not $\displaystyle O(x^3)$ because $\displaystyle x^3\log x \leq Cx^3$ is not compatible with $\displaystyle \log x\to+\infty$. On the other hand $\displaystyle \log x=O(x)$, so that $\displaystyle x^3\log x=O(x^4)$. As a summary, $\displaystyle 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 $\displaystyle O(x^3)$ since $\displaystyle x^{-3}(2x^2+x^3\log x)=2x^{-1}+\log x\to +\infty$.

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

3. 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 $\displaystyle \underset{x\to\infty}{O}(x^n)$.
There is no need for the $\displaystyle x \to \infty$ notation it is implicit in the usual definition of Big-O notation.

RonL

4. 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?
For a description of Big-O notation see the Wikipedia article.

RonL

5. ## 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

6. ## Landau symbol

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?