Skip to main content
4 of 4
deleted 89 characters in body; edited title
user avatar
user avatar

Why is the formal definition of Big O notation formulated as such?

Consider the formal definition:

f(n) = O(g(n))

Why is it not:

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

or

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

since for the Big O analysis, f(n)=2n and g(n)=n are identical?

I am confused by the function f(n) using another function.


Update

Why isn' t the definition as follows:

f(n) <= c*abs(g(n))

What does the formal O(g(x)) add to the definition? It seems like it overcomplicates things.

user10326
  • 1.8k
  • 4
  • 17
  • 18