undefined | Better HN

0 pointstachyoff8y ago0 comments

I wouldn’t call time complexity particularly complex math. Imagine a loop. It does something n times. Within that loop, you do something n times. For each outer looo through n,you do an inner loop through n. Trivially, this is n*n, or n^2, also known as quadratic time. If you nest another loop, it becomes n^3, or cubic time.

Anyway, there might be some confusion of terms, perhaps. Exponential time in the algorithmic complexity sense is any algorithm that takes 2^n operations to complete. If you’re talking about the number of iterations after you loop through n things n times, then that increase itself would not be exponential. But that delta in iterations is unrelated to exponential and polynomial time complexity.

0 comments

austincheney8y ago

I am sooo not a math person.

Let's not forget there is overhead to loops. At a minimum let's assume there is a single statement in the loop body, an increment statement and a terminal condition. In a single loop of 1000 iterations there are 3000 things to evaluate. The math becomes:

(n * 3)^x

If a simple loop is nested twice (3 depths) there would be 1 billion iterations but about 27 billion evaluations. Would it be correct to say that is just slightly faster polynomial growth?

j / k navigate · click thread line to collapse

0 comments

austincheney8y ago

I am sooo not a math person.

(n * 3)^x

If a simple loop is nested twice (3 depths) there would be 1 billion iterations but about 27 billion evaluations. Would it be correct to say that is just slightly faster polynomial growth?

j / k navigate · click thread line to collapse