Asymptotic notation informal definitions

  • Thread starter colt
  • Start date
  • #1
22
0
I was wondering if the O notation definition could be exchanged with the Ω notation and o could be exchanged with the ω notation.

I ask this because of this:
2n² O(n²) means that 2n² <= c*n² which it is true for c=3 and n>=1 for example

Instead, it would be like this:

c*2n² <= n² which would be true for c=1/3 and n>=1 for example

and in the Ω case, 2n² Ω n² means that c*2n² <= n² ,which is true to c=1/3 and n>=1 for example. Instead could it be defined so it would means that 2n² < c*n², which would be true for for c=3 and n>=1, for example. Basically changing the meaning of these notations

The same would be applicable to o and ω notations.

And in the case of n²-2n = θ(n²), instead of c1*n²<=n²-2n<=c2*n² could it be c1*n²-2n<=n²<=c2*n²-2n adjusting the coefficients as needed?

It is all of this valid, or there is some restriction that forces these definitions to be that way?
 

Answers and Replies

  • #2
41
0
I don't think it's possible to know what you are talking about. Could you please try to explain your question over?
 
  • #3
22
0
I will try starting with only the O notation then

for a function f(x) to be O g(x) is necessary that f(x) <= c * g(x) for a certain n >= n0 right?

for f(x) = 2n² to be <= than g(x) = n², you could call c of 3 and n >= 1 for instance.

However, if the definition of O notation were c* f(x) <= g(x), for a certain n>= n0, c could be 1/3 and n>=1 that the inequality would keep being true.

Instead to make g(x) bigger, the idea is to make f(x) smaller.

But if you pay attention to the Ω notation would have noted that it is c* f(x) <= g(x) for n>= n0, exactly the "new" notation for O. So Ω would have to change for not be equal to O.
And so would became f(x) <= c * g(x), that it is the "old" definition of O

So what I am doing here is basically swapping their definitions.

The original Ω is equal to the new O notation
 

Related Threads on Asymptotic notation informal definitions

  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
4K
Replies
3
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
1
Views
942
  • Last Post
Replies
4
Views
17K
Top