Some Questions on Complexity

Question

1) Reorder the following efficiency from smallest to largest: 2^n, n!, n^5, 10000, nlog2(n)

My Ans-> 10000 < nlog2(n) < n^5 < 2^n < n! Correct ?

2) Efficiency of an algo. is n^3, if a step in this algo. takes 1 nanosec. (10^-9 sec.). How long does it take the algo. to process an input of size 1000?

I don't know ... Is it (1000)^3 * 10^-9 ?

Answer 1

Both answers are correct

Answer 2

1) Yes, that's correct.

2) That is also correct. Dimensional analysis: (1000^3 steps) * 10^(-9) seconds/step

Answer 3

Question one is fine. Question two, I would guess your answer is what they're looking for, but if by n^3 you mean O(n^3), you can't actually answer it (unless this is a use of "algorithmic efficiency" I'm unfamiliar with).

Big-O complexity gives an asymptotic bound on the behavior of the algorithm. We know, for "large" n, that O(n^3) is larger than the time taken to execute the algorithm on input of size n. Note the two caveats - "large n" and "asymptotic bound". There's nothing to stop an input of size 1000 taking twice as long as an input of size 2000, as long as there exists some m such that for all n > m, n^3 bounds the runtime. Also, there's nothing to stop the algorithm taking 1 nanosecond on every input, as n^3 is still a bound on the runtime - it's just very pessimistic.

This is why big O notation is often of limited use in practical situations. It gives a fair "worst case" overview, but does not speak to any given usage scenario. For a more practically useful (but often overlooked) complexity class set, google for "Big theta".