How to calculate complexity if a code contains multiple n complexity loops?

Viewed 502

I am a bit confused on the topic of calculating complexity.
I know about Big O and also how to calculate the complexity of loops (nested also).

Suppose I have a program with 3 loops running from 1 to n

for (int i=0;i<n;i++)
{ 
cout << i ; 
}

Now if I ran my CPP code having 3 for loops, will it take 3*n time?

Will the CPP compiler run all the 3 loops at the same time or will do it one after another?
I am very confused on this topic. Please help!

3 Answers

Now if I ran my CPP code having 3 for loops, will it take 3*n time?

Yes, assuming that the time of each loop iteration is the same, but in Big O notation O(3*n) == O(n), so the complexity is still linear.

Will the CPP compiler run all the 3 loops at the same time or will do it one after another?

Implicit concurrency requires a compiler to be 100% sure that parallelizing code will not change the outcome. It can be (and it is, see comments) done for simple operations, but cout << i is unlikely to be parallelized. It can be optimized in different ways however, e.g. if n is known at compile time, compiler could generate the whole string in one go and change the loop into cout << "123456...";.
Also, time complexity and concurrency are rather unrelated topics. Code executed on 20 threads will have the same complexity as code executed on one thread, it will just be faster (or not).

Now if I ran my CPP code having 3 for loops, will it take 3*n time?

Run a thousand loops and still it would be O(n), since while calculating the upper bound time complexity of a function any constant is neglected. So O(n*m) will always be O(n) if m doesn't depend on input size.

Also, the compiler won't run them at the same time, but sequentially one after the other(unless multi-threading, ofc). But even then, 3,10 or 1000 loops one after another will probably be considered O(n) as per the definition as long as the number of times you loop is not dependent on input size.

How to calculate complexity if a code contains multiple n complexity loops?

To understand Big-O notation and asymptotic complexity, it can be useful to resort at least to semi-formal notation.

Consider the problem of finding and upper bound on the asymptotic time complexity a function f(n) based on the growth of n.

To our help, lets loosely define a function or algorithm f being in O(g(n)) (to be picky, O(g(n)) being a set of functions, hence f ∈ O(...), rather than the commonly misused f(n) ∈ O(...)) as follows:

If a function f is in O(g(n)), then c · g(n) is an upper bound on f(n), for some non-negative constant c such that f(n) ≤ c · g(n) holds, for sufficiently large n (i.e. , n ≥ n0 for some constant n0).

Hence, to show that f ∈ O(g(n)), we need to find a set of (non-negative) constants (c, n0) that fulfils

f(n) ≤ c · g(n), for all n ≥ n0,                                (+)

Let's consider your actual problem

void foo(int n) {
    for (int i = 0; i < n; ++i) { std::cout << i << "\n"; }
    for (int i = 0; i < n; ++i) { std::cout << i << "\n"; }
    for (int i = 0; i < n; ++i) { std::cout << i << "\n"; }
}

and for analyzing the asymptotic behaviour of foo based on growth on n, consider std::cout << i << "\n"; as our basic operation. Thus, based on this definition, foo contains 3 * n basic operations, and we may consider foo mathematically as

f(n) = 3 * n.

Now, we need to find a g(n) and some set of constants c and n0 such that (+) holds. For this particular analysis this is nearly trivial; insert f(n) as above in (+) and let g(n) = n:

3 * n ≤ c · g(n), for all n ≥ n0, [let g(n) = n]

3 * n ≤ c · n, for all n ≥ n0,    [choose c = 3]

3 * n ≤ 3 · n, for all n ≥ n0.

The latter holds for any valid n, and we may arbitrarily choose n0 = 0. Thus, as per our definition above of a function f being in O(g(n)), we have showed that f is in O(n).

It is apparent that even if we multiply the loop in foo a multiple of times, as long as this multiple is constant (and not dependent on n itself), we can always find a degenerate number of constants c and n0 that will fulfill (+) for g(n) = n, thus showing that the function f describing the number of basic operations in foo based on n is upper bounded by linear growth.

Now if I ran my CPP code having 3 for loops, will it take 3*n time?

However, it is essential to understand that Big-O notation describes the upper bound on the asymptotic behaviour of a mathematically described algorithm, or e.g. of programmatically implemented function that based on the definition of a basic operation can be described as the former. It does not, however, present an accurate description what runtime you may expect of different variations of how to implement a function. Cache locality, parallelism/vectorization, compiler optimizations and hardware intrinsics, inaccuracy in describing the basic operation are just a few of many factors that make the asymptotic complexity disjoint from actual runtime. The linked list data structure is good example of one where asymptotic analysis is not likely to give a good view of runtime performance (as loss of cache locality, actual size of lists and so on will likely have a larger effect).

For actual runtime of your algorithms, in case you are hitting a bottle neck, actually measuring on target hardware with product representative compiler and optimization flags is key.

Related