Question

What is the time complexity of the following code? (in big-O notaion)
sum = 0

count = 0

var1 = 0

for: i=1 to n{

sum = sum+i

for j=1 to [(3i+2i)(5n)(2i)]{

var1 = sum+count}

}

for m = i to j*j{

sum = sum*sum

var2 = sum - (count+3)}

Answer 1

As we know that big O notation is a fundamental tool to compute the complexity in mathematical term.

so formula would be f(x)<= cg(x) where c is constant , it could be any constant. for example

f(x)= 2x² +3x + 5 <= 20x² +33x + 5

                               <= 20x³ +any thing

                               <= 20x⁴ +33x + anything all would be BigO notation

so now i am comming to the point of question, i have devide whole code in line so that during the interpretation it would be easy to understand.

see the carefully code line 4 it would be go 1 to n , if here i take n=5 the 1 to 5 so line 5 will take constant time when we talk about the big number for n then it would be negligible, now calculate theline 6 and line 9 to 11, normally if we understand of line 6 see

Here third loop is independent , and i and j is defined local variable, if we assume to both varibale independent, so m=i go j*j if j = n then it will go n² so so now we can write as assemble the whole thing :

c(constant)+n³ + n² +c(constant) =O(c*n³)

i hope you got the main thing