(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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

2. Relevant equations

3. 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:

And, here is an example of O(n)Code (Text):int x = 10 // constant run time.

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))Code (Text):for (int i = 0; i < n; i++)

{

print "hello\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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Big O notation (from mathematical perspective)

**Physics Forums | Science Articles, Homework Help, Discussion**