Geek asks and answers

Time complexity when j + = sqrt (i)

I need to find the time complexity (in terms of theta) of this function:

int x = 0; 
for (int i=1; i < n ; i++) { 
  for (double j=i; j <= n ; j+=sqrt(i)) { 
    ++x; 
  } 
}

I know that the outer loop is doing n-1 iterations, and the inner loop is doing (ni) / sqrt (i) iterations, so I need to calculate the sigma i = 1-n-1 of (ni) / sqrt (i). Any idea how to do this?

EDIT: Suppose sqrt () works in O (1).

+3
source share
1 answer

, , sqrt - , O, .. j + = sqrt (i); j + = i; j + = 1;. (n-k) ~ = n k n. , n n-i n. (n-i) * sqrt() = n * 1 = n. n , n ^ 2.

: , , , , , . , O (n ^ 2) K * n ^ 2. , + 2 * +... (n-1) * + n * i. , K 1 +... + n. n, .. n n ~ = (n-1) (n-1) ~ = (n-2), , (n-2) ~ = n. , n , . , C * (n-k) * n + c. C, k c - . , n, n ^ 2. , n ^ k * n, k , n , . ~

0
source

More articles:


All Articles