How many times is print () called depending on the parameter n?

def f5(n): i = n while i > 0: j = i while j > 0: print(i, j) j = j - 1 i = i // 2 def f6(n): i = n while i > 0: j = i while j > 0: print(i, j) j = j // 2 i = i - 1
  • one
    And you just can not start? There will be a sum of logarithms of numbers in the 2nd case and a sum of numbers without the last bits in the first one. - pavel
  • @pavel "just run" even for moderately large n can run for a long time. - jfs

2 answers 2

If T(n) = T(n-1) + c , where T(n) is the number of steps performed by the cycle for a given n , then T(n) = O(n) . If T(n) = T(n/2) + c , then T(n) = O(log(n)) .

In the first case, the inner loop repeats: n + n/2 + n/4 + n/8 + ... ~ n , considering that :

$ sum_ (k = 1) ^ ((log (n)) / (log (2))) n / 2 ^ k = n-1 $

That is, f5(n) is the O(n) algorithm , despite the fact that at first glance the code in f5() may look like the O(n log n) algorithm.

On the other hand, the exact value can be easily found using Python simply by replacing print() in the question code with count += 1 and noting that the nested loop is executed i times , which allows replacing it with count += i :

 def count_f5(n): count = 0 if n >= 0: i = n # abcde # + abcd # + abc # + ab # + a while i: # log(n) iterations count += i i >>= 1 # i //= 2 return count

In the second case: log(n) + log(n-1) + log(n-2) ... ~ log(n!) Times :

$ sum_ (k = 1) ^ n log (k) = log ((1) _n) $

That is, f6(n) is the O(log(n!)) == O(n log n) algorithm.

To get the exact number of print() calls in f6() , it suffices to note that each j //= 2 in a nested loop discards one digit in binary representation j , therefore the total number by iteration in a nested loop is equal to the number of digits in binary representation i , there is i.bit_length() on Python, a method that returns the number of bits in a number.

Then the exact number of print() calls in f6() can be found using the rectilinear cycle of i :

 def count_f6_bruteforce(n): return sum(i.bit_length() for i in range(1, n+1))

This code can be simplified and reduced to an explicit formula :

 def count_f6(n): if n < 1: return 0 # 2**(nbits - 1) <= n < 2**nbits nbits = n.bit_length() return nbits * (n + 1) - 2**nbits + 1
  • I allowed myself to correct your second formula with regard to the Stirling formula. I note that it is not very correct to supplement the original question and give an answer to it - without the consent of the author ... - Harry
  • @Harry: thanks for the pictures. By letter, the question is expanded, but in spirit it is the same question (with more useful wording for this site). If a similar (small) extension of the author does not suit you, you can always roll back. The technique shown in the response works for both formulations. - jfs

Well, it is clear that

enter image description here

and

enter image description here

but how it is written in an analytical form - Knut knows it :) At least in the Concrete Mathematics for the first formula, only the estimates in section 4.4 are given, and it is explained that this sum is very easy to count in binary form, discarding one minor bit ...

Update On the unasked question about the time complexity, of course, did not answer. But if the author is really interested in the answer to this question, then

enter image description here

enter image description here

The first is determined by the fact that the real value

enter image description here

so it is easy to make an assessment both from above and below. A similar estimate is made for the second case, taking into account the Stirling formula

enter image description here

  • The formula for the series is an improvement over the explicit code in question, but this is an incomplete solution if your intention was to find how many times print() called. For example, looking at your series, it’s not obvious what the answer is for n=1000_000 . - jfs