Time complexity which the loop is controlled by condition like i = c^i, c is a constant
a problem about time complexity
int j = 2
while (j < n) {
int k = j
while (k < n) {
sum += a[k] * b[k]
k += n^1/3 * logn
}
j = 2^j
}
The execution time of inner loop seems to be ((n2) / n^1/3 * logn) + 1, however I am not sure how many times the outer loop executes which is controlled by condition j = 2^j. Thank u so much!
1 answer

Assuming
int
is 32bit type, ifn > 65536
, it will run forever because of overflow. Forn <= 65536
, the progression ofj
is2
,4
,16
,65536
, which means that outer loop iterates at most 3 times, not an evergrowing number relative ton
, so outer loop can be considered O(1).