Big O notation (from mathematical perspective)

[skintight]

Homework Statement

Give a clear and concise mathematical definition for Big-O. ("f(n) is O(g(n)) if...")

Homework Equations

The Attempt at a Solution

I'm in a discrete math class and overall I understand the concept of run-time analysis. For example, if a variable is declared it would be O(1) because it is constant no matter on the data set.

Here is an example:

int x = 10 // constant run time.

And, here is an example of O(n)

for (int i = 0; i < n; i++)
{
      print "hello\n"
}

What I don't understand is how to prove this from a mathematical perspective. What screws me up is this wording (yes, all those parenthesis); f(n) is O(g(n))

Is there a way that I can rewrite that statement without the parenthesis, or can someone explain this problem in a different way? I am confident I can solve it but I need to understand it first.

What I think the problem is saying is this.

There are two equations:
- f(n)
- g(n)

Given a problem I need to show the the function / equation f(n) (whatever it is) has a run time of whatever the function / equation g(n) is. Is this correct?

Thanks for any assistance.

 

[grief]

You're not supposed to prove anything. You're only supposed to define big-O notation mathematically.

Here's some facts that might help you:

n=O(4n)
4n=O(n)
n^2=/=O(n)

What's the difference between the first two and the third?

So big O means that the first function is less than or equal to the second function up to a constant. There does not exist a constant c such that n^2<=c*n for all n. That's why n^2=/=O(n). Try to formalize this into a definition

 

[skintight]

oh, thanks grief. i think i have now solved it using your clear explanation. obviously, f(n) has to be less than or equal to to some constant, Z, multiplied by g(n) given that another constant is less then f(n).