Algorithmic linear - log with While. Using big O-CodePudding

How is the complexity of algorithmic?.

I have the next sentences:

m = 12
while m>0:
  n = 0
  while n<m:
     n =1 
  m/=3

I have that complexity is (n 1)(log_3(n)), so O(nlog_3(n) log_3(n)) is the result.

this right?

CodePudding user response：

Replacing m/=3 with m//=3 to ensure working with integer and removing side effects (the time needed for m/3 to round to 0), we can do some tests:

def counter(m):
    count = 0
    while m>0:
      count  = 1
      n = 0
      while n<m:
         n =1
         count  = 1
      m//=3
    return count

Tests:

counter(12)
# 20
counter(1000)
# 1505
counter (1000000)
# 1500006

which points to a complexity of O(1.5 m).

The explanation if simple: the number of iterations (for the inner loop, the number of iterations in the outer loop is negligible) is m m/3 m/3^2 m/3^3 ... , whose mathematical limit is m * 1/(1 - 1/3) = m * 1/(2/3) = 3m/2 .

2 final points:

when evaluating complexity, you don't keep negligible (additive) elements.
a complexity of O(1.5 m) will actually be written O(m) (linear complexity).

CodePudding user response：

The complexity is not O(nlog_3(n) log_2(n)). The outer loop runs until m becomes 0. The number of times the loop is executed is log_3(m).

Inside the loop, the inner loop runs n times, where n is the value of m at the start of each iteration of the outer loop.

The complexity of the algorithm is therefore O(m * log_3(m)).