Hi,
This is running time question. I have got following code snippet:

int count =0;
for(int i=n/2; i<=n; i++)
   for(int j=1; j+n/2<=n;   j=j++)
       for(int k=1; k<=n; k=k*2)
          count++;
}

Q. What is the running time of above code?

I have tried to find the running time of each loop separately:

<for(int i=n/2; i<=n; i++)>
if n=4; then i=2, 3, 4
n=8; then i=4, 5, 6, 7, 8
slighly greater than half so running time is log n.

Now for:

<for(int j=1; j+n/2<=n; j=j++)>
if n=4: then j=1, 2,
n=8; then j=1, 2, 3, 4
Again log n.
And for:

for(int k=1; k<=n; k=k*2)
running time is also log n.

There running time = log n * log n * log n
=O(log(n)^3)

Is this correct. Some body please guide me.

Zulfi.

 

Let's consider just that outer loop.

As a function of n, how many times does the outer loop execute?

It starts at i = n/2 and finishes at i = n, so the number of loops is

t(n) = n - (n/2) + 1 = n/2 + 1

Check: for t(4) = 3 and t(8) = 5, which match your results.

So what is O(t(n))?

 

Hi,
I have asked a question. And you are also asking question instead of answering me. Its puzzling and your question is also puzzling. First solve my puzzle then I would try to solve your puzzle. Is this your homework?

Zulfi.

 

Here's the solution to your "puzzle"

Is this correct?

No.

Somebody please guide me.

Let's consider just that outer loop.

As a function of n, how many times does the outer loop execute?

It starts at i = n/2 and finishes at i = n, so the number of loops is

t(n) = n - (n/2) + 1 = n/2 + 1

Check: for t(4) = 3 and t(8) = 5, which match your results.

So what is O(t(n))?

 

Hi,
If its greater than half then it should be O(n). So O(t(n)) = O(n).

And finally my solution for the problem in post# 1 is: O(n * n * log (n)).

Some body please guide me, if its correct or not.

Zulfi.

 

Hi,
If its greater than half then it should be O(n). So O(t(n)) = O(n).

And finally my solution for the problem in post# 1 is: O(n * n * log (n)).

Some body please guide me, if its correct or not.

Zulfi.

This is progress, but I think you still have an error in your thinking that needs to be addressed.

What do you mean by "if it's greater than half..."?

Let's say s(n) = 0.000001·n + 10000000

What is O(s(n))?

 

Hi,

I think you still have an error in your thinking that needs to be addressed.

Yes you are right. If I have O(n/2), it should be O(n) & similarly O(n/2 - 1) should not be log(n), it would again be O(n). log(n) would come into play if we have a divide by 2 situation in each iteration.

What do you mean by "if it's greater than half..."?

It was my mistake. I have to ignore the constant.

Let's say s(n) = 0.000001·n + 10000000

it should be : O(n)
I have to ignore both the constant: 0.000001 & 10000000.

Zulfi.

 

Very good.