I can usually tell that if something is just assignments, that's constant, and a loop is n, and a nested loop is n^2, n^3, etc.

But then there's something like this:

sum=0; for(int j=1; j<n; j*=2){ sum++; }

Apparently that's O(log(n)), but I have no idea where that comes from. My professor seems to expect that we can just look at an algorithm and just know what it's time complexity is.

And we had a quiz question recently that said, "For the typical algorithm that you use to perform calculations by hand, determine the running time in terms of n to a) add two n-digit numbers, and b ) multiply two n-digit numbers."

I said that adding would be constant, and multiplying would be n. But the right answer is that adding is n, and multiplying is n^2, and I don't understand why.

Is there some method by which I can figure this out?

Help appreciated, thanks!

This post has been edited by **nebulinda**: 11 September 2009 - 02:33 PM