0

I have seen the following pseudocode:

for j=1 to n
    m=n
    while m>0
          //some instructions
          m=m/2

I can see that the outer loop is running n times, but when it gets into the while portion it makes a series of m/2. For example, if n=10 I would get roughly that m will take the values of 10,5,2,1 so approximately it will iterate 4 times; when n=100 the values of m would be 100,50,25,12,7,3,1 so approximately 7 iterations. For what I see that would be log n (with base=2) so the final answer would be: n*log n. Am I right?

The problem that I have is how to get the details of the while loop, I can do something like:

n/2=1
n=2 apply log b=2 to both sides, so I will get:
log (base 2) n=log (base 2) 2
log n=1

I have problems with this last part, what would be the correct mathematical deduction of this section?

Thanks

Little
  • 3,363
  • 10
  • 45
  • 74

2 Answers2

1

You can rewrite the equation as repeated divisions by two.

So we want to find x when n / 2^x = 1 where x is the number of divisions we need to preform (here I will use 1 because in real number arithmetic division by two will never produce zero and a 1 approximation is good enough for an upper bound)

Rearranging we get n = 2^x so now taking the log we have we have log(n) = x. So the x we need to reach 1, and therefore the time complexity for the inner loop is log(n)

Mitch
  • 3,342
  • 2
  • 21
  • 31
1

Let K represent the number of inner loops. So, 2^K approximately equal to n. Thus, the number of inner loops is K = log(2^K) = log(n).

To run the entire algorithm, Sum[log(n)] loops are required. This is equivalent to log[Pi(n)] = log(n!).

Asymptotically, this is O(n log(n)) as shown in this SE question.

Jared Goguen
  • 8,772
  • 2
  • 18
  • 36