I need help in this question. I really don't understand how to do it.
Show, either mathematically or by an example, that if f(n) is O(g(n)), a*f(n) is O(g(n)), for any constant a > 0.
4
-
2What do you have so far?Nico Huysamen– Nico Huysamen2011-04-29 06:10:19 +00:00Commented Apr 29, 2011 at 6:10
-
Homework? If so, the relevant tag is missingNeowizard– Neowizard2011-04-29 06:10:30 +00:00Commented Apr 29, 2011 at 6:10
-
You should add homework to your tags.Skyler Saleh– Skyler Saleh2011-04-29 06:11:01 +00:00Commented Apr 29, 2011 at 6:11
-
is this homework? If yes, please tag it as such. Also, what is your problem? Do you understand what O(...) means? Have you looked at its formal definition?MarcoS– MarcoS2011-04-29 06:11:47 +00:00Commented Apr 29, 2011 at 6:11
Add a comment
|
1 Answer
I'll give you this. It should help you look in the right direction:
definition of O(n):
a function f(n) who satisfies f(n) <= C*n for an arbitrary constant number C and for every n above an arbitrary constant number N will be noted f(n) = O(n).
This is the formal definition for big-o notation, it should be simple to take this and turn it into a solution.
5 Comments
Marco
Yes it is homework, Im sorry this is my first time using stackoverflow.com, and I didn't know what it meant by tags
Marco
We are barely learning about big-O notation and asymptotic analysis. I got this question in my homework and it didn't explain it was about O(n), so that is why I'm a confuse. I really don't know how my answer should be.
Neowizard
I don't think that an upright solution will be given here. Working out your homework yourself will help you a bunch in the long run. That said, help is always available, just ask a specific question. For starters, see how you can take your function f(n) and see what f(n) = O(g(n)) says about it (according to the big-o definition above)
Marco
That is the problem I don't understand what f(n) or g(n) means. A function of what? A normal function in mathematics? what does O mean in this problem ( ex:O(g(n)) )?
Neowizard
I gave you the definition/meaning of O (A.K.A big-o notation), and as for g(n) and f(n), they are general mathematical functions. All you need to know about them is that they are an expression made out of constants(numbers) and a parameter names "n" combined with mathematical operators (+, -, log, power etc). It's not important what's the expression, so just think about it as what ever you like to call it (expression, function, black box or whatever). This is a simple question in complexity, so don't let it confuse you, just try what you can.