alice

06-05-2004, 10:49 PM

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

12

2n^2 + 3 n

5 n lg n + 4 n

View Full Version : Using big-O notation

alice

06-05-2004, 10:49 PM

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

12

2n^2 + 3 n

5 n lg n + 4 n

laserlight

06-06-2004, 12:39 AM

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)

12 => O(1)

2n^2 + 3 n => O(n^2)

5 n lg n + 4 n => O(n log n)

XSquared

06-06-2004, 12:50 AM

I think that the third one is O(n), but I'm not sure.

electRONix

06-06-2004, 02:04 AM

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)

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)

Zach L.

06-08-2004, 03:10 PM

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).

Speedy5

06-08-2004, 03:13 PM

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.

alice

07-05-2004, 04:05 AM

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?

since nlgn<n2<n3

f(n)=5 n lg n + 4 n < 5(n3)+4n

=19n

am I correct?

laserlight

07-05-2004, 04:38 AM

hmm... I dont understand your reasoning.

f(n) is 5n lg n + 4n

f(n) is 5n lg n + 4n

Zach L.

07-05-2004, 10:11 AM

n3 should be n^3... That is, n cubed, not three times n

Powered by vBulletin® Version 4.2.5 Copyright © 2019 vBulletin Solutions Inc. All rights reserved.