CODEWITHSUNDEEP
algorithmtime-complexitybig-o
shauryachats
shauryachats

Reputation: 10385

Time Complexity Of This Code Snippet

Recently, I came across a code snippet:

int i = 1;
while (N > 1)
{
        N = N / i;
        i = i + 1;
}

On observation, it was evident that i increases linearly, and i divides N in every runtime of the loop, hence we could say that N reduces as a function of an inverse function of a factorial.

How would we represent this in the theta notation, as inverse factorial is not defined for every natural number N? Would we have to suffice by using the approximate upper and lower bounds of this function?

Upvotes: 7

Views: 1097

Answers (2)

FreeNickname
FreeNickname

Reputation: 7764

Well, I'm not sure, but I'll give it a shot. The factorial is, in essence, a gamma function. And gamma function is defined not only for natural numbers, but also for real numbers. So, there is, in theory, a inverse gamma function, which is defined for cases, where factorial is undefined (for instance, we don't know the inverse factorial of 5, but we know, that the inverse gamma function of 5 will be something around two-point-something). According to MathOverflow, there is no precise formula for the inverse gamma function, but there are approximate solutions.

Let's just suppose that inverse gamma function exists, and let's write it as InvGamma(N). It is an real number (might be R+, but I'm not sure, it's not important now, since our N is always positive, apart of N == 0 case, which I will ignore for now).

Then we can use it the same way as we use other functions that return a real number, when we deal with complexity: we can floor it (round it down). Just like we do with log complexity. I used to write using square brackets (i.e. log(15) = 1.18, [log(15)] = 1).

Then the complexity of your snippet should be O([InvGamma(N)]), I believe.

UPDATE: (inspired by @6502's answer): note that if N is an integer (it's not mentioned in the code snippet), then there will be a rounding on every step, which alters complexity in a complicated way. The solution above works for real Ns.

Upvotes: 4

6502
6502

Reputation: 114481

The "natural" extension of factorial to all complex plane except negative integers is called "gamma function" and on all non-negative integers gamma(n) = (n-1)!.

You could therefore invert a portion of gamma to compute the approximate number of iterations needed but I'm not sure this would lead to an exact computation of the number of iterations as in that code there is a rounding operation at every step.

Upvotes: 1

Related Questions