5

I know that in terms of complexity, O(logn) is faster than O(n), which is faster than O(nlogn), which is faster than O(n2). But what about O(n2) and O(n2log), or O(n2.001) and O(n2log):

T1(n)=n^2 + n^2logn

What is the big Oh and omega of this function? Also, what's little oh? versus:

T2(n)=n^2.001 + n^2logn

Is there any difference in big Oh now? I'm having trouble understanding how to compare logn with powers of n. As in, is logn approximately n^0.000000...1 or n^1.000000...1?

Joseph D
  • 115
  • 7
  • 2
    I think the key point you are missing is this: `log(n)` grows slower than any positive power of `n`, however small that power may be. So `log(n)` isn't approximately *any* power of `n`. – Michael J. Barber Sep 29 '15 at 15:28
  • One thing you can say: `log(n) = n^{o(1)}`. That is, it is asymptotically smaller than `n^{epsilon}` for any `epsilon > 0`. – Chris Beck Sep 29 '15 at 16:57

2 Answers2

3

O(n^k) is faster than O(n^k') for all k, k' >= 0 and k' > k

O(n^2) would be faster than O(n^2*logn)

Note that you can only ignore constants, nothing involving the input size can be ignored.

Thus, complexity of T(n)=n^2 + n^2logn would be the worse of the two, which is O(n^2logn).

Little-oh

Little oh in loose terms is a guaranteed upper bound. Yes, it is called little, and it is more restrictive.

n^2 = O(n^k) for k >= 2 but n^2 = o(n^k) for k > 2

Practically, it is Big-Oh which takes most of the limelight.

What about T(n)= n^2.001 + n^2logn?

We have n2.001 = n2*n0.001 and n2 * log(n).

To settle the question, we need to figure out what would eventually be bigger, n0.001 or log(n).

It turns out that a function of the form nk with k > 0 will eventually take over log(n) for a sufficiently large n.

Same is the case here, and thus T(n) = O(n2.001).

Practically though, log(n) will be larger than n0.001.

(103300)0.001 < log(103300) (1995.6 < 3300), and the sufficiently large n in this case would be just around 103650, an astronomical number.

Worth mentioning again, 103650. There are 1082 atoms in the universe.

axiom
  • 8,765
  • 3
  • 36
  • 38
  • But what about T(n)= n^2.001 + n^2logn – Joseph D Sep 29 '15 at 13:49
  • Your plot is misleading. Any power of `n` dominates `log(n)`. With such a slowly growing function as `n^0.001`, it's going to take an enormous value for `n` before the lines cross, though. – Michael J. Barber Sep 29 '15 at 15:37
  • @axiom I eliminated the common factor of `n^2` from each. – Michael J. Barber Sep 29 '15 at 16:44
  • Incidentally, I tried plotting out the curves on *logarithmic* axes, and they still haven't crossed when I reach the limit of the largest floats my graphing program can handle. So any number representable as a double is still in the "small enough that constant factors matter" regime; that includes such piddling small numbers as the number of possible chess board configurations or the number of atoms in the observable universe. – Michael J. Barber Sep 29 '15 at 17:19
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/90952/discussion-between-axiom-and-michael-j-barber). – axiom Sep 30 '15 at 05:36
1

T(n)=n^2 + n^2logn

What is the big Oh and omega of this function? Also, what's little oh?

Quoting a previous answer:

Don't forget big O notation represents a set. O(g(n)) is the set of of all function f such that f does not grows faster than g, formally is the same is saying that there exists C and n0 such that we have |f(n)| <= C|g(n)| for every n >= n0. The expression f(n) = O(g(n)) is a shorthand for saying that f(n) is in the set O(g(n))

Also you can think of big O as ≤ and of small o as < (reference). So you care of more of finding relevant big O bound than small o. In your case it's even appropriate to use big theta which is =. Since n^2 log n dominates n^2 it's true that 

T1(n)=n^2 + n^2logn = Ө(n^2 logn)

Now the second part. log n grows so slowly that even n^e, e > 0 dominates it. Interestingly, you can even prove that lim n^e/(logn)^k=inf as n goes to infinity. From this you have that n^0.001 dominates log n then 

T2(n)=n^2.001 + n^2logn = Ө(n^2.001).

If f(n) = Ө(g(n)) it's also true that f(n) = O(g(n)) so to answer your question:

  • T1(n)=O(n^2 logn)
  • T2(n)=O(n^2.001)
Community
  • 1
  • 1
sve
  • 4,336
  • 1
  • 19
  • 30