complexity of code

Question

what is the complexity of a program having only one loop, is it log n? can someone give me some ideas about estimating complexity of codes?

Answer 1

Well, that really depends on what is going on in that loop.

This loop is linear time, i.e., O(n):

int sum = 0;
foreach( int i in SomeCollection )
{
    sum += i;
}

However, consider a loop which performs a substring search during each iteration. Now you have to consider the complexity of the string searching algorithm. Your question can't be answered as it stands. You will need to provide a code sample if you want a meaningful answer.

Answer 2

Software Complexity

There is a field of study that attempts to quantify exactly that.

It's called cyclomatic complexity.

In this case, I believe your complexity rating would be p = 2, because the loop is conditional and that means there are two paths through the method.

Time complexity

If you are referring to time complexity, it's still just O(1) unless the loop iteration count is derived via a polynomial or exponential function, perhaps indirectly because the method is itself called in a higher loop, or because the loop counter is effectively multiplied by string operations or something at a lower level.