0

What I need is to an explanation on how to determine it, here are few examples and hope you can help me find their complexity using Big-O Notation:

For each of the following, find the dominant term(s) having the sharpest increase in n and give the time complexity using Big-O notation.  
Consider that we always have n>m.

Expression Dominant term(s) O(…) 
5+ 0.01n^3 + 25m^3   
500n +100n^1.5 + 50nlogn   
0.3n+ 5n^1.5  +2.5n^1.75   
n^2logn +n(log2m)^2    
mlog3n +nlog2n   
50n+5^3 m + 0.01n^2
Jeremy W
  • 1,889
  • 6
  • 29
  • 37
  • 5
    There are a few explanations of Big O, which you may or may not have read. [Big O, how do you calculate](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it?rq=1) and [Plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o?rq=1). The rest of the posed question is for someone here to do what appears to be homework for you. – KevinO Apr 14 '16 at 16:32
  • 1
    I'm voting to close this question as off-topic because, as a theoretical question, it belongs on a site such as Computer Science.SE – Darwin von Corax Apr 14 '16 at 22:32

1 Answers1

1

It's fairly simple.

As n rises to large numbers (towards infinity), some parts of the expression becomes meaningless, so remove them.

Also, O() notation is relativistic, not absolute, meaning there is no scale, so constant factors are meaningless, so remove them.

Example: 100 + 2*n. At low numbers 100 is the main contributor to the result, but as n increases, it becomes meaningless. Since there is no scale, n and 2n is the same thing, i.e. a linear curve, so the result is O(n).

Or said another way, you choose the most extreme curve in the expression from this graph:
(source: bigocheatsheet.com)

Let's take your second example: 500n +100n^1.5 + 50nlogn
1st part is O(n).
2nd part is O(n^1.5).
3rd part is O(nlogn).
Fastest rising curve is O(n^1.5), so that is the answer.

Community
  • 1
  • 1
Andreas
  • 154,647
  • 11
  • 152
  • 247
  • Thank you so much for your detailed answer, it really helped me figure out some steps, but as you can see there are other examples, where we have different types and there's another variable [m]. how do I calculate it in those other cases? Thanks again. –  Apr 14 '16 at 16:53
  • I'm not going to do all your homework for you. Maybe you should read this section: https://en.wikipedia.org/wiki/Big_O_notation#Properties – Andreas Apr 14 '16 at 17:12
  • @Moudi the other variable is its own dimension, following the same rules. So the first one would be O(n^3 + m^3) – Carlos Apr 14 '16 at 20:17