analysing time complexity of my programs

Question

I have problem in determining time complexities of algorithms.

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

for(int i= 0 ;i<n ;i++){    O(n^2)
  for(int j=0;j<n;j++){ 

  }
}

Now for following code whats the complexity

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

is it O(2n) as it invloves 2 seperate loops?

what if i start j =5 to n?

Answer 1

There is no O(2n), it's just O(n). In other words, it scales at the same rate as n increases.

If it was a nested loop, it would be O(n2) but the presence of your {} empty blocks means it isn't nested.

And it makes no difference whether you start at one or five, it still scales with n, just with a slightly negative constant addition. Hence still O(n).

The complexities O(n), O(cn) and O(n+c) (where c is a constant) are all equivalent. In addition, you also generally only use the term with the highest effect.

So you won't usually see O(7n3 + 3n2 + 12n + 2), that will be simplified to O(n3).

Answer 2

There is no such thing as O(2n). Time complexity refers to how an algorithm scales to infinity, not to its actual running time. In your examples, you have two loops that are both linear [ O(n) ] time, meaning that they will scale linearly with the input, hence your overall algorithm is O(n).

If you start j=5, it's still O(n) because it still scales linearly.

So in essence, O(2n) == O(n).