0 votes
int j = 2
while (j < n) {
    int k = j
    while (k < n) {
        Sum += a[k] * b[k]
        k += n^(1/3) log(n)
    }
    j = j * sqrt(5)
}

From the midterm practice
in Asymptotic Analysis by AlgoMeister (684 points)

1 Answer

+3 votes
 
Best answer

Outer loop Analysis (for j)

j goes from 2 to n, multiplied by a constant at ever stype

n = (2 * sqrt(5)) * sqrt(5)).... = 
Therefore, number of steps = 2log[5,(n/2)] = O(log(n))
Inner loop Analysis (for k) 

n = k * n^(1/3)* log(n) 
Number of steps: O(n^(2/3)/log(n))
Overall:
O(log(n) * n^(2/3)/log(n)) 
= O(n^(2/3))
by AlgoMeister (684 points)
selected by
Sorry for the poor formatting.  This site doesn't seem to work very well with super / subscripts and added a new line whenever i attempted to use one
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...