Time Complexity ?

[algo_man]

I've two algorithms and I want some one to explain the time complexity for each one.

First Algorithm:
---------------------------------

m = n
for i=1 to n
    if m is even then
        for j=1 to log n
          count++
        end for
   end if
m=m/2
end for

----------------------------------
What is the time complexity for the first algorithm? with explain please ????

Second Algorithm:
---------------------------------

while(m>1) do
    if m is even then
       for j=1 to log n
         count ++
       end for
    end if
end while

---------------------------------
What is the time complexeity for the second algorithm? with explain

What is the different between them?

And what is the best and easy way to know that?

[Rashakil Fol]

First you need to describe what the '/' operator does: integer division or floating point division? Then you need to count the total number of fundamental operations that each algorithm executes, in terms of the variables at hand. Unless you've never found the running time of an algorithm before, you should be able to figure these out with some careful consideration. The first algorithm looks hard, but you can look closely at its constituent parts. The second algorithm: its running time should be very easy to analyze, if you understand the principle of counting how many fundamental operations the algorithm takes to compute.

[algo_man]

Thank you Rashakil Fol

First algorithm deal with integer numbers and m/2 means m over 2

But could you please guide me to the right way to count the number of operation ?

I can try to find it by counting the number of iterations, but some time is will be complex to understand ...

I think you get my point !!

[Infarction]

m = n
for i=1 to n
    if m is even then
        for j=1 to log n
          count++
        end for
   end if
m=m/2
end for

For this one, you'll run the outer loop n times (1 to n). For a large integer n, you'll end up running the inner loop most of the time, and it iterates log n times. So, for each iteration of the outer loop, you do log n work; since there's n iterations of the outer loop, you multiply them and get O(n log n).

while(m>1) do
    if m is even then
       for j=1 to log n
         count ++
       end for
    end if
end while

For m>1, this doesn't end. For m<=1, it runs in constant time, since it never executes the loop.

You should read this page for a description of time complexity.

[algo_man]

I am not completely agree with you in the first algorithm

m = n
for i=1 to n
    if m is even then
         for j=1 to log n
         count++
         end for
    end if
    m=m/2
end for

Since, we have m=m/2 , and the outer loop will continue till n.
But when m=1 then the inner loop doesnt work

use iterations to see that:

---------------------------------------------------
m               i            inner loop
---------------------------------------------------
m               1            log n
m/2            2            log n
m/4            3            log n
m/2^k-1     k            log n
1                k+1        C
1                k+2        C
. . .
. . .
. . .
and so on

and finally we get log n * log n + c*n - log n

So, O(n)

And for the Second Algorithm, I am sorry I made a mistake in it, so it should be:
-------------------------------------------

while(m>1) do
       if m is even then
           for j=1 to log n
           count ++
           end for
           m=m/2
      end if
end while

-------------------------------------------

[Infarction]

I am not completely agree with you in the first algorithm
...
Since, we have m=m/2 , and the outer loop will continue till n.
But when m=1 then the inner loop doesnt work

but then we come to m=m/2 again, and 1/2 == 0, so m == 0, and m is even. So from there the inner loop will always run.

And for the Second Algorithm, I am sorry I made a mistake in it, so it should be:
-------------------------------------------

while(m>1) do
       if m is even then
           for j=1 to log n
           count ++
           end for
           m=m/2
      end if
end while

-------------------------------------------

if m is odd and greater than 1, it'll have an infinite loop still. Maybe you meant this:

while(m>1) do
       if m is even then
           for j=1 to log n
           count ++
           end for
      end if
      m=m/2
 end while

in which case, the outer loop will run log(m) times and the inner one will run (worst case) each of those times. At log(n) for the inner loop, we get O( log(m) * log(n) )