'What is the time complexity of this pseudo-code

sum = 0
for i in range(1, n+1, 1):
    for j in range(1, n+1, 1):
        if j % i > 0:
            for k in range(1, j+1, 1):
                sum += 1

based on what i have done so far we have:

sum = 0                                   -> 1
for i in range(1, n+1, 1):                -> n+1
    for j in range(1, n+1, 1):            -> n(n+1)
        if j % i > 0:                     -> n(n)
            for k in range(1, j+1, 1):    -> (n)(n) j+1
                sum += 1                  -> (n)(n) j

the time complexity will be O(j n^2) but i have some trouble figuring out the value of j.

we also have:

(times line 5 was executed) - (times line 6 was executed) = sum n-floor(n/i), i=2 to n

algorithm


Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source

Related Questions