How to get the time complexity of these algorithms, in terms of n in quiz 2?

+2 votes

j= 2
while (j < n) {

k=2
while (k < n) {

Sum += a[k]*b[k]

k = k * sqrt(k) }

j += 5*j/3 } 

and 

for (int j = 1 to n) { int k = j

while (k < n) {
Sum += a[k]*b[k] k += n
1/3

} } 

asked Feb 18 in Asymptotic Analysis by liyanbo Active (312 points)

1 Answer

+1 vote
 
Best answer

My answer would be O(logn * log log n) for #1 and O(n5/3) for #2.  I don't know about others, I have an alternative way to quantify time complexity: the total times for executing each line of code. 

Explanation: 

#1: for the inner loop

while (k < n) {
            Sum += 1;            
            k = k * sqrt(k);     
        }

How many iterations will be executed depends on value k, in this loop, k starts as 2, goes with 23/2, (23/2)3/2, .... , 2(3/2)^z, until it becomes greater than n. the value z here is the times of iteration, assume 2(3/2)^z = n, there exists z = log log n.

For the outer loop, 

    while (j < n) {
        k = 2;
       //inner loop, takes log log n

        ...

        j += 5*j/3;
    }

Similarly, j starts as 2, goes with 2, 5/3 * 2, (5/3)2 * 2, ...., (5/3)z * 2, until it becomes greater than n. the value z = log5/3n/2, approximately, log n.

The time complexity of the total algorithm is the product of each loop, which is O(log n * log log n).

#2: I take k += n1/3  as k += n1/3. Again, for inner loop, k starts as j, goes with j + n1/3, j + 2 * n1/3, ... , j + z * n1/3 until it becomes greater than n. (omit constant z) the value z = n2/3. For the outer loop. j starts as 1 to n, so z = n. For the whole algorithm , it's O(n5/3).

We can't accurately calculate each algorithm manually, because constant will be omitted during the process, the base number of log will always count as 2, etc. However, we can know the order of magnitude after doing some simple math, which is the meaning of O().

answered Feb 20 by Ethan Huang AlgoMeister (648 points)
selected May 4 by liyanbo
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...