algorithm - how i can find the time complexity of the above code -

 for(i=0; i<n; i++) // time complexity n+1 {     k=1;   // time complexity n     while(k<=n) // time complexity n*(n+1)     {     for(j=0; j<k; j++) // time complexity ??      printf("the sum of %d , %d is: %d\n",j,k,j+k); time complexity ??     k++; } 

what time complexity of above code? stuck in second (for) , don't know how find time complexity because j less k , not less n.

i having problems related time complexity, guys got article on it? step count , loops.

from question :

because j less k , not less n.

this plain wrong, , guess that's assumption got stuck. know values k can take. in code, ranges 1 n (included). thus, if j less k, less n.

from comments :

i know the input n in second depends on k not in n .

if variable depends on anything, it's on input. j depends on k depends on n, means j depends on n.

however, not enough deduce complexity. in end, need know how many times printf called.

the outer loop executed n times no matter what. can factor out.

the number of executions of inner loop depends on k, modified within while loop. know k takes every value 1 n once. means inner loop first executed once, twice, 3 times , on, until n times.

thus, discarding outer loop, printf called 1+2+3+...+n times. sum known , easy calculate : 1+2+3+...+n = n*(n+1)/2 = (n^2 + n)/2.

finally, total number of calls printf n * (n^2 + n)/2 = n^3/2 + n^2/2 = o(n^3). that's time complexity.

a final note kind of codes. once see same patterns few times, start recognize kind of complexity involved. then, when see kind of nested loops dependent variables, know complexity each loop linear.

for instance, in following, f called n*(n+1)*(n+2)/6 = o(n^3) times.

for (i = 1; <= n; ++i) {     (j = 1; j <= i; ++j) {         (k = 1; k <= j; ++k) {              f();         }     } }