Javascript Question

How does multiple for loops in the same scope affect a program's big O notation?

So let's say I had a program that looked like this:

var foo = 10;

for(var i = 0; i < foo; i++){
console.log('first loop');

for(var j = 0 j < foo; j++){
console.log('second loop');

Now, from what I understand about Big O notation in general, we measure the efficiency(aka how long it takes to run) of a program based on the size of the N input. So if the 'j' loop were nested within the 'i' loop, this would make it n^2, but because both loops are in the same scope, the runtime would still be O(N). Is this assessment correct?

Answer Source

Yes your assumption is correct,

The basic operation done here in both loop is

  • Loop 1, Iteration 1
  • Loop 1, Iteration 2 .......
  • Loop 1, Iteration 10
  • Loop 2, Iteration 1 .......
  • Loop 2, Iteration 10

for each loop of order N there is N write operation.

so total time complexity will be O(N) + O(N) but since constants are ignored so the complexity is O(N)

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download