What is the complexity of running a loop twice of the same input array?

Question

I am new to Algorithms, and very much interested in learning and implementing them.
Learning them through all available online materials i can find. I am a little confused regarding this -

Consider this code -

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

What will be the complexity of this ?
O(n) or O(n^2) ?

Suppose the running time of the first loop was n = 5 units. What do you expect the total running time to be, 10 units (2*n) or 25 units (n^2)? — Jeroen Mostert
– Jeroen Mostert, Commented Jun 11, 2016 at 16:07
Generally, I've always thought of it as nested loops you multiply and consecutive loops you add. Constants drop out of the final complexity — OneCricketeer
– OneCricketeer, Commented Jun 11, 2016 at 16:11

Gordon Linoff · Accepted Answer · 2016-06-11 16:07:42Z

13

Assuming that the { . . . } is constant time, then the complexity of one loop is O(n).

What is the complexity of two "adjacent" loops? It is O(n) + O(n). Or you could think of this as O(n + n) --> O(2n). Constants drop out of complexity, so this is O(n).

It is an entirely different matter with nested loops. So the following:

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

would be O(n^2).

answered Jun 11, 2016 at 16:07

Gordon Linoff

1.3m62 gold badges705 silver badges857 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

mohangraj Over a year ago

As you mentioned "Constants drop out of complexity" means only if Constant is less than n value? Because if n = 5, then On^2 = 25 as well as O(5n) also 25?

Gordon Linoff Over a year ago

@mrg . . . You are missing something. n doesn't have a value. It varies up to infinity. Hence, a constant is always less than n. Constants are constant. Complexity is based on what happens in the limit as n --> infinity.

Vatsal Prakash · Accepted Answer · 2016-06-11 17:15:24Z

3

The complexity will remain O(n)

(Assuming that you don't have another loop inside those for loops).

answered Jun 11, 2016 at 17:15

Vatsal Prakash

5586 silver badges17 bronze badges

Comments

Cereal_Killer · Accepted Answer · 2016-06-11 18:18:50Z

The idea behind calculating time complexity is how many time your loop/function is executing each step inside of it ?
for example: for loop

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

the code in curly braces will print n times hello so the time complexity of this for loop will be O(n)

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

this will print hello 2 time more than the previous as it have two for loop. time complexity is O(2n). We ignore the constants while computing time complexity so the time complexity will be O(n)

for ( int i=0; i < n; i++ ) {
    for ( int j=0; j < n; j++ ) {
        cout << "hello" << endl;
    }
}

this will print hello n^2 time, why ? because for each outer for loop (i) you execute inner for loop(j) O(n) time. so O(n^2)will be time complexity

read further http://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/

Collectives™ on Stack Overflow

What is the complexity of running a loop twice of the same input array?

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related