Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Asymptotic notation informal definitions

  1. Dec 20, 2012 #1
    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?
     
  2. jcsd
  3. Dec 22, 2012 #2
    I don't think it's possible to know what you are talking about. Could you please try to explain your question over?
     
  4. Dec 23, 2012 #3
    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Asymptotic notation informal definitions
  1. Notation (Replies: 2)

Loading...