Is there any effective way to analyse the inner loop's time complexity(Big-O)?

kizzy 0
Viewed 35
int j=2;
int sum=0;
while(j<n){
    int k=j;
    while(k<n){
        sum+=k;
        k*=k;
    }
    j+=log(k);
}

I meet some trouble when I analyse the inner loop's time complexity.

time-complexity
1 Answers

Notice that the sequence of values k takes on across the loop is j, j2, j4, j8, etc. More generally, across m iterations of the loop, the value of k is j2m.

The loop stops when k exceeds n. Equating, rearranging, and using properties of logarithms gives us that

j2m = n

2m = logj n = log n / log j

m = log (log n / log j) = log log n - log log j

In other words, the inner loop runs a total of log log n - log log j iterations.

templatetypedef0
Related