Find the value of p

Question

Consider following program and determine the value of p after execution of program:-

main()
{
    p = 1;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j=5*j)
        {
            p = p + n;
        }
    }
}

I think p's final value should be p = 1+n²log₅n.

Comments

@just_bhavana

The value of p = 1+n²(FLOOR(log₅n)+1)

---

Yes, when n is not an exact power of 5, we'll have to consider floor

---

And also when n is perfectly divisible by 5.

Answer 1

1 + n²(log₅n +1)

Answer 2

Time complexity will be O(n log₅n ) because.

1. The inner loop is independent of the outer loop. For each value of i  It will run log₅n each time.

so, for n times it will be = O(n log₅n ).

for(i=1;i<=n;i++) =================================== O(n)
    {
        for(j=1;j<=n;j=5*j) { =======================log

₅n p = p + n; } }

Because inner loop doesn't depend on the on the outer loop so, directly multiply here O(n log₅n ).