Как мы можем найти большие обозначения O для конечных нулей в факториале?

Question

Я знаю, как рассчитать большие нотации для факториала, но мне сложно объединить обе нотации. это код для расчета конечных нулей.

using namespace std;

  // Function to return trailing 
  // 0s in factorial of n
 int findTrailingZeros(int n)
 {
   // Initialize result
    int count = 0;

    // Keep dividing n by powers of 
    // 5 and update count
    for (int i = 5; n / i >= 1; i *= 5)
        count += n / i;

    return count;
}

// Driver Code
int main()
{
   int n = 100;
   cout << "Count of trailing 0s in " << 100
        << "! is " << findTrailingZeros(n);
   return 0;
}

Answer 1

Сложность O(log(n)).Легко увидеть, если вы нанесете число итераций для каждого n:

n        iterations
------   -----------
< 5      0
< 25     1
< 125    2
< 625    3
< 3125   4