I was given this time complexity assignment for my computer science class and I

Question

I was given this time complexity assignment for my computer science class and I mostly understand how to calculate the time complexity but these two I am just a little confused on. I know the first for loop for question E) would be O(N) and the second I know runs 1 less time every iteration so I guess that would be n-1 but I am really not sure. Question F) I think it's N^3 since you have N*N in the second loop which is N^2 then times N again gives you N^3 but once again I am not entirely sure, so a good explanation on how time complexity would work would be awesome!

E) for (int x=0; x < n; x++)

for (int y=x; y < n; y++)

System.out.print(“*”);

(F) for (int x=0; x < n; x++)

for (int y=0; y < n * n; y++)

System.out.print(“*”);

Explanation / Answer

in question E,

when x=0 , y loop executes for n times, x=1 n-1 times and so on upto x=n when y loop runs 1 times, TOTAL = sum of numbers from 1 to n = n/2*(n+1) = hence time complexity is O(n^2)

: in question F ,

when x=0 , y loop executes for n^2 times , x=1 y loop runs for n^2 -1 times ,and so on upto x=n when y loop runs for 1 times , so TOTAL = sum of n ( n^2) - sum of numbers from 1 to n =( n*n^2) - (n/2*(n+1)) ,hence time complexity = O(n^3)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.