Determining and analysis the big-O runtimes of these different loops

Question

here is the simple code, i want to find out the time complexity of the code i have already done analysis on it, my teacher told me that there is a mistake in it. i am not able to figure out where i am wrong. need a help in it. thanks

j = 2
while(j<n)
{
    k=j
    while(k < n) 
    {
        sum + = a[k]*b[k]
        k = k*k
    }
    k = log(n)
    j += log(k)
}

here what i got the answer

time complexity = O(n/loglogn).

i just want to know where i am wrong

Well, you've shown not much of analysis, rather an answer, so it's hard to guess where you are wrong — YakovL, Sep 19 '16 at 23:18

score 0 · Answer 1 · edited May 23 '17 at 10:27

You go from 2 to n, adding log log n to the accumulator each step, so you do indeed have n / log log n steps.

However, what is done per step? Each step, you go from j to n, multiplying the accumulator by itself each step. How many operations is that? I'm not 100% sure, but based on messing around a bit and on this answer, this seems to end up being log log (n - j) steps, or log log n for short.

So, n / log log n steps, doing log log n operations each step, gives you an O(n / log log n * log log n), or O(n) algorithm.

Some experimentation seems to more or less bear this out (Python), although n_ops appears to flag a bit as n gets bigger:

import math

def doit(n):
    n_ops = 0

    j = 2
    while j < n:
        k = j
        while k < n:
            # sum + = a[k]*b[k]
            k = k*k
            n_ops += 1

        k = math.log(n, 2)
        j += math.log(k, 2)
        n_ops += 1

    return n_ops

Results:

>>> doit(100)
76
>>> doit(1000)
614
>>> doit(10000)
5389
>>> doit(100000)
49418
>>> doit(1000000)
463527

so what should be the time complexity of it according to you? — Justin Hawry, Sep 19 '16 at 21:58

score 0 · Answer 2 · answered Sep 19 '16 at 23:40

Ok. Let's see. The

k=j
while(k < n) 
{
    sum + = a[k]*b[k]
    k = k*k
}

bit takes what takes j^(2^i) to reach n. I.e. what 2^i takes to reach log_j(n) which is log_2(log_j(n)). Now you have

j = 2
while(j<n)
{
    // stuff that takes log_2(log_j(n))
    j += log(log(n))
}

This would require n/log(log(n)) of steps but those steps take different time. If they took equal time, you would be right. But instead you have to sum for {j from 2 to n/log(log(n))} log_2(log_j(n)) which is

sum for {j from 2 to n/log(log(n))} [log_2(log(n)) - log_2(log(j))]

which is not that simple. Well, at least, I think I've pointed where you are probably wrong, which was the question.

Determining and analysis the big-O runtimes of these different loops

2 Answers2