Skip to main content
added 94 characters in body
Source Link
Falcon
  • 19.4k
  • 4
  • 81
  • 93

I am confused on defining the function f(n) using another function

Don't be confused, it's actually pretty simple. The big O notation is an inequation. That means that we can find multiple upper bounds for f(n) and still be correct, hence, although we can write f(n) = O(f(n)) and be correct it's, depending on f(n), often not what we are intending to express.

It's a measure of growth rates. f(n) = 2n does not grow faster than f(n) = n. Both growths are linear.

f(n) = O(n*f(n))

I'll assume you meant the second n to be a constant c.

By definition of Big O, this constant is already in the inequation. So when you write the usual f(n) equals Big O you're actually writing c * abs(g(xn)) you're actually writing abs(f(n)) <= c * abs(g(n)). If you can find a constant factor you needn't mention it, because the definition of Big O, the inequation, already takes care of that and g(n) is then considered an upper bound of f(n).

Maybe the common wording can help you: f(n) = O(g(n)) means the function f does not grow faster than g, except maybe for a constant factor c.

I am confused on defining the function f(n) using another function

Don't be confused, it's actually pretty simple. The big O notation is an inequation. That means that we can find multiple upper bounds for f(n) and still be correct, hence, although we can write f(n) = O(f(n)) and be correct it's, depending on f(n), often not what we are intending to express.

It's a measure of growth rates. f(n) = 2n does not grow faster than f(n) = n. Both growths are linear.

f(n) = O(n*f(n))

I'll assume you meant the second n to be a constant c.

By definition of Big O, this constant is already in the inequation. So when you write the Big O you're actually writing c * abs(g(x)). If you can find a constant factor you needn't mention it, because the definition of Big O, the inequation, already takes care of that.

I am confused on defining the function f(n) using another function

Don't be confused, it's actually pretty simple. The big O notation is an inequation. That means that we can find multiple upper bounds for f(n) and still be correct, hence, although we can write f(n) = O(f(n)) and be correct it's, depending on f(n), often not what we are intending to express.

It's a measure of growth rates. f(n) = 2n does not grow faster than f(n) = n. Both growths are linear.

f(n) = O(n*f(n))

I'll assume you meant the second n to be a constant c.

By definition of Big O, this constant is already in the inequation. So when you write the usual f(n) equals Big O(g(n)) you're actually writing abs(f(n)) <= c * abs(g(n)). If you can find a constant factor you needn't mention it, because the definition of Big O, the inequation, already takes care of that and g(n) is then considered an upper bound of f(n).

Maybe the common wording can help you: f(n) = O(g(n)) means the function f does not grow faster than g, except maybe for a constant factor c.

Source Link
Falcon
  • 19.4k
  • 4
  • 81
  • 93

I am confused on defining the function f(n) using another function

Don't be confused, it's actually pretty simple. The big O notation is an inequation. That means that we can find multiple upper bounds for f(n) and still be correct, hence, although we can write f(n) = O(f(n)) and be correct it's, depending on f(n), often not what we are intending to express.

It's a measure of growth rates. f(n) = 2n does not grow faster than f(n) = n. Both growths are linear.

f(n) = O(n*f(n))

I'll assume you meant the second n to be a constant c.

By definition of Big O, this constant is already in the inequation. So when you write the Big O you're actually writing c * abs(g(x)). If you can find a constant factor you needn't mention it, because the definition of Big O, the inequation, already takes care of that.