Big O question related to nested loop

Question

So i have code that is a nested loop and the outside loop executes n times but the inside loop executes $n\sqrt{n}$ times. So would my worst case scenario still be $O(n^2)$?

Answer 1

If the inner loop runs $$\sqrt n$$ times and outer loop runs n times as you indicated in you comments then you get: $$n\cdot \sqrt n = n^{3/2}$$ Since $$f=O(g)$$ means that your f grows no faster than g, it follows that $$n^{3/2}=O(n^{3/2})$$ i.e. there is a constant C that makes g grow faster than f.

Answer 2

It seems that the worst (and the best) scenario will give $n^2\sqrt n$ times.

Answer 3

It would be $\Omega(n^{2})$ time, but not $O(n^{2})$ time. The intuition for this is that you multiply the complexities of inner loops.

Consider as well, straight from the definition of Big-O. Suppose your algorithm was $O(n^{2})$. Then $n * n\sqrt{n} \leq C * n^{2}$, for some positive constant $C$. We then get that $\sqrt{n} \leq C$, which we know not to be true.

You can derive the runtime function $T(n)$ for your algorithm yourself, but these are good tricks to eye-ball it.

Edit: Now that you've clarified the inner loop runs in $\sqrt{n}$ time, you would be correct that $n\sqrt{n} \in O(n^{2})$.

Here is a really good tutorial on basic Big-O analysis of code: http://www.dreamincode.net/forums/topic/125427-determining-big-o-notation/