CODEWITHSUNDEEP
pythontime-complexity
Pwaol
Pwaol

Reputation: 206

How to find the time complexity of this function?

def f1(n):
   cnt = 0
   for i in range(n):
      for j in range(n):
         k = 1
         while k < i*j:
            k *= 2
            cnt += 1
  return cnt

I am trying to analyze the time complexity of this function f1, I'm having some troubles dealing with the k < i*j in the loop.
My point of view:
I'm trying to find the number of iterations of the inner loop, so what I'm basically trying to find is when 2^k >= i*j, but I'm having trouble dealing in how to compute i*j each time and find the overall time complexity. I know that at the end I will have 2^k >= n^2 which gives me k >= log(n) , but I must be missing all the iterations before this and I would be happy to know how to calculate them.

Any help is really appreciated, Thanks in advance!

EDIT:
With Prune's help I reached this: We're trying to calculate how many times the inner loop iterates, which is log(i*j).
taking i=2 we get log(2) + log(j) (n times) which is n + log(1)+log(2)+...+log(n).
So we have n+log(n!) for each i=0,1,...,n basically n(n+log(n!)). Which is either O(n^2) or O(nlog(n!)). as it's my first time meeting log(n!) I'm not sure which is considered to be the time complexity.

Upvotes: 0

Views: 96

Answers (1)

Prune
Prune

Reputation: 77837

For convenience, let m = i*j. As you've noted, you execute the while loop log(m) times.

The complexity figure you're missing is the summation:

sum([log(i*j)
        for j in range(n)
        for i in range(n)])

Would it help to attack this with actual numbers? For instance, try one iteration of the outer loop, with i=2. Also, we'll simplify the log expression:

sum([log(2) + log(j) for j in range(n)])

Using base 2 logs for convenience, and separating this, we have

n*1 + sum([log(j) for j in range(n)])

That's your start. Now, you need to find a closed form for sum(log(j)), and then sum that for i = 0,n

Can you take it from there?

After OP update

The desired closed form for sum(log(j)) is, indeed, log(n!)

This isn't simply "go n times`: it's the sum of log(i)*n + log(n!) over the range.

Upvotes: 1

Related Questions