tags:

views:

168

answers:

2

I have the hardest time with Big Oh Notation. I was wondering if you could help me out. Whats the least upper bound of the growth rate using big-Oh notation of these two functions?

n   f(n)
----------
5   18
10  35
15  53
20  70
25  88
30  105
35  123
40  140

n   g(n)
-----------
5   240
10  1990
15  6740
20  15990
25  31240
30  53990
35  85740
40  127990
+1  A: 

n -> f(n) looks like O(c*n) = O(n)

n -> g(n) ~ O(2*n^3) = O (n^3)

Dutow
A: 

Well the first one looks a lot like o(n), as an 8 fold increase in n results in an approx 8 fold increase in f(n).

The second one looks like roughly n^3

Visage
exponential? That's a^n, not n^a...
Dutow
You're right. I've edited accordingly.
Visage