What is the time complexity for this algorithm?

Question

public static void Comp(int n)
{
    int count=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            for(int k=1;k<n;k*=2)
            {
                count++;
            }
        }
    }
    System.out.println(count);
}

Does anyone knows what the time complexity is?

And what is the Big Oh()

Please can u explain this to me, step by step?

I think it's N^2 * logN.

Luiggi Mendoza
– Luiggi Mendoza

2015-04-07 16:19:31 +00:00
Commented Apr 7, 2015 at 16:19 — Luiggi Mendoza
– Luiggi Mendoza, Commented Apr 7, 2015 at 16:19

halfer · Accepted Answer · 2019-10-20 19:45:41Z

1

Whoever gave you this problem is almost certainly looking for the answer n^2 log(n), for reasons explained by others.

However the question doesn't really make any sense. If n > 2^30, k will overflow, making the inner loop infinite.

Even if we treat this problem as being completely theoretical, and assume n, k and count aren't Java ints, but some theoretical integer type, the answer n^2 log n assumes that the operations ++ and *= have constant time complexity, no matter how many bits are needed to represent the integers. This assumption isn't really valid.

Update

It has been pointed out to me in the comments below that, based on the way the hardware works, it is reasonable to assume that ++, *=2 and < all have constant time complexity, no matter how many bits are required. This invalidates the third paragraph of my answer.

edited Oct 20, 2019 at 19:45

halfer

20.2k20 gold badges111 silver badges208 bronze badges

answered Apr 7, 2015 at 16:52

Paul Boddington

37.8k10 gold badges69 silver badges120 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Konsol Labapen Over a year ago

That's usually the assumption, which is not incorrect. Multiplication by 2 is just a shift operation in hardwhare and ++ is just a counter, which is a constant clock cycle. check out teahlab.com especially the counter articles/circuits. So the question is not as theoretical as you might think. In hardware the assumptions are correct.

Katedral Pillon Over a year ago

accepting this as the answer shows just how lost and confused the OP is. The question is not as theoretical as this guy assumes, and he just mentions that the other answers are correct. So how is this the correct answer? A little thinking, friend. A little thinking.

Katedral Pillon Over a year ago

@KonsolLabapen for the shift operation (i.e. multiply by 2), would the Parallel access shift register work? teahlab.com/4-Bit_Parallel_Access_Shift_Register I went to the site and search for the word shift and that's what came up.

Konsol Labapen Over a year ago

You would need a much bigger one than 4-bit, but yea. It should work for shifting and any large counter for counting.

Konsol Labapen Over a year ago

This is certainly an interesting discussion. If you look at the way gates work (by gates I mean integrated circuits): gates are not aware of each other. There is no cascading propagation in a shift register. Each gate looks at its input. And when the clock cycle comes in, at that instant each gate computes based on its input signal. So you can have a billion gates. If they are arranged in parallel, they will all compute simultaneously on the clock. So yes O(1) is actually correct. And these shift registers can be purchased at your local hardware store, so nothing special really.

|

pkacprzak · Accepted Answer · 2015-04-07 16:23:45Z

1

In theory this is O(n^2 * log(n)).

Each of two outer loops is O(n) and the inner one is O(log(n)), because log base 2 of n is the number of times which you have to divide n by 2 to get 1.

Also this is a strict bound, i.e the code is also Θ(n^2 * log(n))

answered Apr 7, 2015 at 16:23

pkacprzak

5,6131 gold badge20 silver badges37 bronze badges

Comments

Community · Accepted Answer · 2020-06-20 09:12:55Z

1

The time complexity is O(n^2 log n). Why? each for-loop is a function of n. And you have to multiply by n for each for loop; except the inner loop which grows as log n. why? for each iteration k is multiplied by 2. Think of merge sort or binary search trees.

details

for the first two loops: summation of 1 from 0 to n, which is n+1 and so the first two loops give (n+1)*(n+1)= n^2+2n+1= O(n^2)

for the k loop, we have k growing as 1,2,4,8,16,32,... so that 2^k = n. Take the log of both sides and you get k=log n

Again, not clear?

enter image description here

So if we set m=0, and a=2 then we get -2^n/-1 why is a=2? because that is the a value for which the series yields 2,4,8,16,...2^k

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Apr 7, 2015 at 16:19

Konsol Labapen

2,4342 gold badges17 silver badges12 bronze badges

3 Comments

user406009 Over a year ago

Incorrect, the most inner for loop takes log(n), making the final product O(n^2 log(n))

G. Bach Over a year ago

He probably wants the tightest bound one can give, which this one isn't.

Luiggi Mendoza Over a year ago

@G.Bach I hardly believe that the most inner loop is O(N).

Collectives™ on Stack Overflow

What is the time complexity for this algorithm?

3 Answers 3

Update

8 Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Update

8 Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related