Answer to Question #186811 in Algorithms for Haider

Question

Analyze the time complexity of the following segments

Program:

sum1=0;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

sum1++

sum2=0;

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

sum2++

Answer 1

sum1=0;
for(i=1;i<=n;i++)       // executed n times
    for(j=1;j<=n;j++)   // executed n times for every i
        sum1++;         // executed n+n+...+n = n*n times


sum2=0;
for(i=1;i<=n;i++)       // executed n times
    for(j=1;j<=i;j++)   // executed i times for every i
        sum2++;         // executed 1+2+...+n = n*(n+1)/2 times

As multipliers and lower powers are insignificant for the purpose of for time complexity the overall complexity is O(n^2)