What is time complexity of below code?

Question

For(I=1 ; I<=n ; I++)
{
    For(J=1 ; J<=I ; J++)
        {
             For(K=1 ; K<=n^5 ; K=15 × K)
                 {
                      x=y+z;
                 }
        }  
}

It seems to be O(N^2 log N) according to me, but when i analyzed the k loop, it is not following the Log N, which is confusing me,

Answer 1

It should be O(n^2 log(n)) because the inner loop will be called (n/2)(n+1) times and it will loop log base 15 of n^5 = 5 * log base 15 of n because k grows exponentially in the number of loops.

This results in 5(n^2+n)(log base 15 of n)/2 assignments to x, which is O(n^2 * log(n))

Answer 2

Time complexity of your problem is:

Explanation:

When we say

we mean

not

2 base of log function is coming from divide by 2 in the definitions inside of for loops about binary searching not from the binary nature of computers.

But in your case divide by value is not 2 but 15 because of k = 15 × k definition so the base of log function must be 15 not 2.

You can see the correlation between these with replacing k *= 15 line with k *= 2 and

print n * n * int(math.log(n**5,15) + 1)

line with

print n * n * int(math.log(n**5,2) + 1)

in the given Python Code above. Results will continue to match.

Also because of the quitting of binary base you need to round up log function with nearest integer function:

Python Code:

import math

n = 100
i = 1
while i <= n:
    j = 1
    while j <= i:
        k = 1
        counter = 1
        while k <= n**5:
            x = 1 + 1
            k *= 15
            counter += 1
        #print k
        #print counter
        j += 1
    #print j
    i += 1
#print i

print "\nTime Complexity Prediction:"
print n * n * int(math.log(n**5,15) + 1)

print "\nReal World Result:"
print (i - 1) * (j - 1) * (counter - 1)
print ""

Example results of the program:

For n = 10:

Time Complexity Prediction:
500

Real World Result:
500

For n = 100:

Time Complexity Prediction:
90000

Real World Result:
90000

For n = 1000:

Time Complexity Prediction:
13000000

Real World Result:
13000000

For n = 3000:

Time Complexity Prediction:
135000000

Real World Result:
135000000