Sorting Algorithms By Efficiency

Question

Guys I have one last question on my homework.. The problems asks:

Reorder the following efficiencies from smallest to largest:
2^n
n!
n^5
10,000
nlog(n)

Again.. Please DO NOT ANSWER This directly.

My Questions:

1.) What does smallest to largest mean? Least Efficient to Most Efficient?

2.) Given that 10,000 is constant, I would assume this to be my most efficient, followed by nlog(n), followed by n!, then efficient n^5, and 2^n last. Would this be correct?

Because it's a timed homework assignment.. he even said don't worry about it being right or wrong, just give it your best shot, but I really want to understand the material, and I think hearing from you guys helps me learn. — HashHazard
– HashHazard, Commented Jan 23, 2013 at 17:29
@MBarnett is "giving it your best shot" asking it here ? To really understand the material you have to study it yourself. — mmgp
– mmgp, Commented Jan 23, 2013 at 17:36
@mmgp he doesn't like the text, so we don't use it and my math skills aren't strong enough to comprehend the google answers i'm getting.. you guys seem to be able to make it understandable so I usually look here first — HashHazard
– HashHazard, Commented Jan 23, 2013 at 17:41

Reinstate Monica -- notmaynard · Accepted Answer · 2013-01-23 17:34:52Z

3

For the cases of n!, n^5, and 2^n, consider how they are increased at n+1, that is, compare (n+1)! to n!, (n+1)^5 to n^5, and 2^(n+1) to 2^n.

As for your first question, interpret as you think makes the most sense and be sure to explicitly state that that is how you're ordering them (least efficient to most or the other way around) so that your professor knows what you mean.

answered Jan 23, 2013 at 17:34

Reinstate Monica -- notmaynard

5,4892 gold badges29 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Daniel Brückner · Accepted Answer · 2013-01-23 18:28:28Z

2

f(n) = O(g(n)) means that |f(n)| is always smaller than or equal to c * |g(n)| for some constant c and sufficiently large n. This means you are comparing the function values as n goes to infinity.

For example 100 * n is less than n² for small n but from n = 100 on n² is always greater than or equal to 100 n and therefore is considered "larger".

It does not work the other way round - no matter how large you choose the constant c there will always be some n0 so that for all n > n0 n² > c * 100 * n. If you for example choose c = 1,000,000 n² is still larger than or equal to c * 100 * n from n = 100,000,000 on.

edited Jan 23, 2013 at 18:28

answered Jan 23, 2013 at 17:34

Daniel Brückner

59.8k16 gold badges103 silver badges144 bronze badges

Comments

mlstudent · Accepted Answer · 2013-01-23 19:25:54Z

1

Try plotting them if you can. See what the graphs look like and compare them, using x instead of n.

answered Jan 23, 2013 at 19:25

mlstudent

9592 gold badges15 silver badges32 bronze badges

Comments

Bill the Lizard · Accepted Answer · 2013-01-23 17:30:08Z

0

What does smallest to largest mean? Least Efficient to Most Efficient?

I would say probably Most Efficient to Least Efficient, so O(1) -> O(n) -> O(n²) order.

Given that 10,000 is constant, I would assume this to be my most efficient, followed by nlog(n), followed by n!, then efficient n^5, and 2^n last. Would this be correct?

Just a hint here. Substitute several values of n for each of these and see which of them grows fastest. Make sure to use a fairly wide spread of values, like the first 7 or 8 powers of 10.

answered Jan 23, 2013 at 17:30

Bill the Lizard

407k213 gold badges579 silver badges892 bronze badges

7 Comments

HashHazard Over a year ago

After taking your advice I changed the order to-- 1)10K, 2.)nlog(n) 3.) 2^n 4.) n^5 5.) n! --- does that look right?

HashHazard Over a year ago

@mmgp could you shed some light?

Bill the Lizard Over a year ago

@MBarnett You might not have used large enough values of n. Will n^5 always be greater than 2^n, or will you eventually hit an n where 2^n is greater? Same question for n!.

HashHazard Over a year ago

@BilltheLizard now I see what you meant when you said 7 or 8 powers of 10... that being said 3.)n^5 4.) n! 5.) 2^n ---?

Bill the Lizard Over a year ago

#3 is right. Does 2^n eventually get bigger than n!? My spreadsheet won't display numbers big enough. :)

|

Itay Karo · Accepted Answer · 2013-01-23 17:29:47Z

0

I'd go the other way around - sort from most efficient to least efficient, but as Johnny commented - ask the professor :)
The first 2 are correct - then you got is scrambled out.

answered Jan 23, 2013 at 17:29

Itay Karo

18.4k4 gold badges43 silver badges59 bronze badges

Comments

BenMorel · Accepted Answer · 2014-01-29 17:41:27Z

0

For this homework just substitute with large inputs and compare. For you to learn.. there is Big O , Omega notation & Theta Θ.

Big O is what you should get for this homework since this is upper bound which your function will never ever exceed ,.. in big values.

Omega Ω is lower bound which is what the function will never go below for small value. 1,000,000 for example.

Theta Θ is something in between.

But in real life I always faced big O notation only.

let n = 1000    
2^n =~ 1e30  
n!  =~ too BIG!  
n^5 =~ 1e15  
10,000 =~ 10000  
nlog(n) 3000

with some sense you will find out the right order now.

edited Jan 29, 2014 at 17:41

BenMorel

37k52 gold badges208 silver badges339 bronze badges

answered Jan 23, 2013 at 18:18

blackmath

2621 silver badge10 bronze badges

Collectives™ on Stack Overflow

Sorting Algorithms By Efficiency

6 Answers 6

Comments

Comments

Comments

7 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

Comments

Comments

7 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related