1

I am currently learning about big O notation but there is a concept that's confusing me. If for 8N^2 + 4N + 3 the complexity class would be N^2 because this is the fastest growing term. And for 5N the complexity class is N.

Then is it correct to say that of NLogN the complexity class is N since N grows faster than LogN?

The problem I'm trying to solve is that if configuration A consists of a fast algorithm that takes 5NLogN operations to sort a list on a computer that runs 10^6 operations per seconds and configuration B consists of a slow algorithm that takes N**2 operations to sort a list and is run on a computer that runs 10^9 operations per second. for smaller arrays configuration 1 is faster, but for larger arrays configuration 2 is better. For what size of array does this transition occur?

What I thought was if I equated expressions for the time it took to solve the problem then I could get an N for the transition point however that yielded the equation N^2/10^9 = 5NLogN/10^6 which simplifies to N/5000 = LogN which is not solvable.

Thank you

Valentin Lorentz
  • 9,556
  • 6
  • 47
  • 69
Mrfuzzy
  • 163
  • 7

5 Answers5

2

In mathematics, the definition of f = O(g) for two real-valued functions defined on the reals, is that f(n)/g(n) is bounded when n approaches infinity. In other words, there exists a constant A, such that for all n, f(n)/g(n) < A.

In your first example, (8n^2 + 4n + 3)/n^2 = 8 + 4/n + 3/n^2 which is bounded when n approaches infinity (by 15, for example), so 8n^2 + 4n + 3 is O(n^2). On the other hand, nlog(n)/n = log(n) which approaches infinity when n approaches infinity, so nlog(n) is not O(n). It is however O(n^2), because nlog(n)/n^2 = log(n)/n which is bounded (it approches zero near infinity).

As to your actual problem, remember that if you can't solve an equation symbolically you can always resolve it numerically. The existence of solutions is clear.

Samuel Peter
  • 4,136
  • 2
  • 34
  • 42
1

Let's suppose that the base of your logarithm is b, so we are to compare

5N * log(b, N)

with

N^2

5N * log(b, N) = log(b, N^(5N))

N^2 = N^2 * log(b, b) = log(b, b^(N^2))

So we compare

N ^ (5N) with b^(N^2)

Let's compare them and analyze the relative value of (N^5N) / (b^(N^2)) compared to 1. You will observe that after a sertain limit it is smaller than 1.

Lajos Arpad
  • 64,414
  • 37
  • 100
  • 175
0

Q: is it correct to say that of NLogN the complexity class is N?

A: No, here is why we can ignore smaller terms:

Consider N^2 + 1000000 N

For small values of N, the second term is the only one which matters, but as N grows, that does not matter. Consider the ratio 1000000N / N^2, which shows the relative size of the two terms. Reduce to 10000000/N, which approaches zero as N approaches infinity. Therefore the second term has less and less importance as N grows, literally approaching zero.

It is not just "smaller," it is irrelevant for sufficiently large N.

That is not true for multiplicands. n log n is always significantly bigger than n, by a margin that continues to increase.

Kenny Ostrom
  • 5,639
  • 2
  • 21
  • 30
0

Then is it correct to say that of NLogN the complexity class is N since N grows faster than LogN?

Nop, because N and log(N) are multiplied and log(N) isn't constant.

N/5000 = LogN

Roughly 55.000

Diane M
  • 1,503
  • 1
  • 12
  • 23
0

Then is it correct to say that of NLogN the complexity class is N since N grows faster than LogN?

No, when you omit you should omit a TERM. When you have NLgN it is, as a whole, called a term. As of what you're suggesting then: NNN = (N^2)*N. And since N^2 has bigger growth rate we omit N. Which is completely WRONG. The order is N^3 not N^2. And NLgN works in the same manner. You only omit when the term is added/subtracted. For example, NLgN + N = NLgN because it has faster growth than N.

The problem I'm trying to solve is that if configuration A consists of a fast algorithm that takes 5NLogN operations to sort a list on a computer that runs 10^6 operations per seconds and configuration B consists of a slow algorithm that takes N**2 operations to sort a list and is run on a computer that runs 10^9 operations per second. for smaller arrays configuration 1 is faster, but for larger arrays configuration 2 is better. For what size of array does this transition occur?

This CANNOT be true. It is the absolute OPPOSITE. For small N values the faster computer with N^2 is better. For very large N the slower computer with NLgN is better.

Where is the point? Well, the second computer is 1000 times faster than the first one. So they will be equal in speed when N^2 = 1000NLgN which solves to N~=14,500. So for N<14,500 then N^2 will go faster (since the computer is 1000 times faster) but for N>14,500 the slower computer will be much faster. Now imagine N=1,000,000. The faster computer will need 50 times more than what the slower computer needs because N^2 = 50,000 NLgN and it is 1000 times faster.

Note: the calculations were made using the Big O where constant factors are omitted. And the logarithm used is of the base 2. In algorithms complexity analysis we usually use LgN not LogN where LgN is log N to the base 2 and LogN is log N to the base 10.

However, referring to CLRS (good book, I recommend reading it) the Big O defines as: Big O

Take a look at this graph for better understanding:

graph

It is all about N > No. So all the rules of the Big O notation are valid FOR BIG VALUES OF N. For small N it is NOT necessarily correct. I mean, for N=5 it is not necessary that the Big O will give a close approximation on the running time.

I hope this gives a good answer for the question.

Reference: Chapter3, Section1, [CLRS] Introduction To Algorithms, 3rd Edition.

Everyone
  • 1,751
  • 13
  • 36