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
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 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 .
That said, means no more than for some and for large enough . I'll neglect the subscript under the O in the following (but write it on your paper anyway!).
Because , what you have to do is only to look at the largest term (when tends to ). 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 (it is larger than , which dominates ). This term is not because is not compatible with . On the other hand , so that . As a summary, and it is not since .
For b), remember .
For c), you can use (or look at the limit as tends to ).
For d), cf. a) and c).
For a description of Big-O notation see the Wikipedia article.
RonL
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