Whats the least upper bound of the growth rate using big-Oh notation of these two functions

Go To StackoverFlow.com

0

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
2009-06-16 07:40
by erickreutz


1

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

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

2009-06-16 07:45
by Dutow


1

f(n) = ceil(3.5*n) which is a member of O(h(n)),

g(n) = 2*n^3-10 which is a member of O(h(n^3))

2012-08-02 04:59
by friendlyautomaton


0

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

2009-06-16 07:50
by PaulJWilliams
exponential? That's a^n, not n^a.. - Dutow 2009-06-16 07:55
You're right. I've edited accordingly - PaulJWilliams 2009-06-16 07:58
Ads