#include "stdio.h"

int main(int argc, const char *argv[])
{
    int n;

    printf("Input a number: ");
    scanf("%d", &n);

    for (int i = 1; i <= n; i *= 3)
        for (int j = i; j <= n; j  )
            printf("Anjali \n");

    return 0;
}

I'm trying to generate a formula for the number of times printf() is executed.

Example: When n = 10;

printf() is executed 20 times

CodePudding user response：

In for (int i = 1; i <= n; i *= 3), i takes on the values of 3^k for non-negative integers k such that 3^k ≤ n, hence k ≤ log₃ n, so k takes on the values 0, 1,… ⌊log₃ n⌋. (⌊x⌋ is the floor of x, the greatest integer not greater than x. Also, we assume n is positive.)

In each iteration of the outer loop, the inner loop for (int j = i; j <= n; j ) is executed, resulting in the printf being executed n−i 1 times. In an iteration of the outer loop, i is 3^k, so, over all the iterations of the outer loop, printf is executed sum(n−3^k 1 for 0 ≤ k ≤ ⌊log₃ n⌋) times.

This sum is (n 1)•(⌊log₃ n⌋ 1) − sum(3^k for 0 ≤ k ≤ ⌊log₃ n⌋). The latter term is a geometric sequence whose sum is (3^{⌊log₃ n⌋ 1}−1)/(3−1). So the printf is executed (n 1)•(⌊log₃ n⌋ 1) − (3^{⌊log₃ n⌋ 1}−1)/2 times.