How can I re-express the below thress functions of algorithm complexity using the big-O notation?
12
2n^2 + 3 n
5 n lg n + 4 n
How can I re-express the below thress functions of algorithm complexity using the big-O notation?
12
2n^2 + 3 n
5 n lg n + 4 n
I havent studied complexity theory formally yet, but my guesses:
12 => O(1)
2n^2 + 3 n => O(n^2)
5 n lg n + 4 n => O(n log n)
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
I think that the third one is O(n), but I'm not sure.
Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah
You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie
I'm taking a theory of algorithms class ...
yeah the third one should be O(nlgn) since the nlgn part grows faster than the linear part. You always want to take the big O of what grows the fastest.. for example
n + n^3 would be O(n^3)
the first one is constant time so that is O(1) and the second one is quadratic time, O(nē) .. to be more precise there is also a theta function (for example while O(n) means the function is less than some constant times n, theta(n) means the function is just about the same as n. That's probably more detail then you needed so stick to
O(1)
O(nē) and
O(nlgn)
Last edited by electRONix; 06-06-2004 at 02:13 AM.
my spider-sense be tingling.
Ron - SCU Math/CS Major
You can take a quick limit to see which grows faster. That is, (n * lg n) / n = lg n which is unbounded as n grows. So, O(n lg n) > O(n).
In general, take the highest order term in the polynomial, strip its coeficient and thats the Big-O efficiency. Remember, logarithms are exponents (inverse though) so this also applies for them.
for the third '5 n lg n + 4 n'
since nlgn<n2<n3
f(n)=5 n lg n + 4 n < 5(n3)+4n
=19n
am I correct?
Last edited by alice; 07-05-2004 at 04:09 AM.
hmm... I dont understand your reasoning.
f(n) is 5n lg n + 4n
Look up a C++ Reference and learn How To Ask Questions The Smart Way
n3 should be n^3... That is, n cubed, not three times n
