CODEWITHSUNDEEP
data-structures
0x82
0x82

Reputation: 29

trouble in finding time complexiy of simple for loop statement

i am new in coding and got problem in finding time complexity of simple for loop consider

for (int i=0;i<n;i++)

i have seen in some sites that the time complexity of above is 2n + 2 and as far what i understood 

    1 for assignment i=0
    n+1 for comparision of i<n

but in case of i++ n times for i++ since the loop will iterate for n times given in some sites

so total time complexity `= 1+(n+1)*2 +n`

but i have problem as i++ =i+1 (which is an arthemetic operation and assignment ) that is it require 2 operation that means n*2 total operation so total time complexity = 1+(n+1)*2 +2n

please help me to find out the correct result

Upvotes: 0

Views: 34

Answers (2)

LibertyPaul
LibertyPaul

Reputation: 1167

for(int i = 0; i < N; ++i)

If the loop body complexity is:

  • O(1): so loop complexity is O(N)
  • O(M): so loop complexity is O(N * M)
  • O(N): so loop complexity is O(N ^ 2)

and so on.

Upvotes: 1

michaJlS
michaJlS

Reputation: 2510

Increment can be done with one operation, e.g.: http://www.tutorialspoint.com/assembly_programming/assembly_arithmetic_instructions.htm

Upvotes: 0

Related Questions