Return to Answer

I'm not sure the approximation above $(LOG_2n)*(LOG_2LOG_2n)$ is correct.

Let's formulate the task in the folllowing way:

We have some number N>2,and we can divide it  by $LOG_2 (N)$ while we get a number that is smaller or equal to 2. How many iterations do we need?

For $N>4$ $LOG_2(N)>2$,so,if we have sufficiently large N-- let's divide it by log(N) each time while we get a number which is <= 4. The number of iterations we will apply before we get a number that is smaller than 4 is <= $LOG_2(N)$(because we divide by a number which is larger than 2 each time),while for N<4 the number of iterations is constant (Actually it is 1 ) and and we can ignore it for sufficiently large N.

So,it means we have O(LogN) as an upper bound.

So,the exercise from the book is solved. But, just out of curiosity, I'm interested more in some method to solve the equation and to get the exact solution. I'm not sure we can replace the difference equation with the differential equation here.

I'm not sure the approximation above $(LOG_2n)*(LOG_2LOG_2n)$ is correct.

Let's formulate the task in the folllowing way:

We have some number N>2,and we can divide it  by $LOG_2 (N)$ while we get a number that is smaller or equal to 2. How many iterations do we need?

For $N>4$ $LOG_2(N)>2$,so,if we have sufficiently large N-- let's divide it by log(N) each time while we get a number which is <= 4. The number of iterations we will apply before we get a number that is smaller than 4 is < $LOG_2(N)$(because we divide by a number which is larger than 2 each time),while for N<4 the number of iterations is constant (Actually it is 1 ) and and we can ignore it for sufficiently large N.

It means we have O(LogN) as an upper bound.

So,the exercise from the book is solved. But, just out of curiosity, I'm interested more in some method to solve the equation and to get the exact solution. I'm not sure we can replace the difference equation with the differential equation here.

I'm not sure the approximation above $(LOG_2n)*(LOG_2LOG_2n)$ is correct.

Let's formulate the task in the folllowing way:

We have some number N>2,and we can divide it  by $LOG_2 (N)$ while we get a number that is smaller than 2. How many iterations do we need?

For $N>4$ $LOG_2(N)>2$,so,if we have sufficiently large N-- let's divide it by log(N) each time while we get a number which is <= 4. The number of iterations we will apply before we get a number that is smaller than 4 is <= $LOG_2(N)$(because we divide by a number which is larger than 2 each time),while for N<4 the number of iterations is constant (Actually it is 1 ) and and we can ignore it for sufficiently large N.

So,it means we have O(LogN) as an upper bound.

So,the exercise from the book is solved. But,just out of curiosity,I'm interested more in some method to solve the equation and to get the exact solution. I'm not sure we can replace the difference equation with the differential equation here.

I'm not sure the approximation above $(LOG_2n)*(LOG_2LOG_2n)$ is correct.

Let's formulate the task in the folllowing way:

We have some number N>2,and we can divide it  by $LOG_2 (N)$ while we get a number that is smaller or equal to 2. How many iterations do we need?

For $N>4$ $LOG_2(N)>2$,so,if we have sufficiently large N-- let's divide it by log(N) each time while we get a number which is <= 4. The number of iterations we will apply before we get a number that is smaller than 4 is <= $LOG_2(N)$(because we divide by a number which is larger than 2 each time),while for N<4 the number of iterations is constant (Actually it is 1 ) and and we can ignore it for sufficiently large N.

So,it means we have O(LogN) as an upper bound.

So,the exercise from the book is solved. But, just out of curiosity, I'm interested more in some method to solve the equation and to get the exact solution. I'm not sure we can replace the difference equation with the differential equation here.

I'm not sure the approximation above $(LOG_2n)*(LOG_2LOG_2n)$ is correct.

Let's formulate the task in the folllowing way:

We have some number N>2,and we can divide it  by $LOG_2 (N)$ while we get a number that is smaller than 2. How many iterations do we need?

For $N>4$ $LOG_2(N)>2$,so,if we have sufficiently large N-- let's divide it by log(N) each time while we get a number which is smaller than 4. The number of iterations we will apply before we get a number that is smaller than 4 is smaller than $LOG_2(N)$(because we divide by a number which is larger than 2 each time),while for N<4 the number of iterations is constant and we can ignore it for sufficiently large N.

So,it means we have O(LogN) as an upper bound.

But,i'm interesting more in some method to solve the equation and to get the exact solution. I'm not sure we can replace the difference equation with the differential equation here.

I'm not sure the approximation above $(LOG_2n)*(LOG_2LOG_2n)$ is correct.

Let's formulate the task in the folllowing way:

We have some number N>2,and we can divide it  by $LOG_2 (N)$ while we get a number that is smaller than 2. How many iterations do we need?

For $N>4$ $LOG_2(N)>2$,so,if we have sufficiently large N-- let's divide it by log(N) each time while we get a number which is <= 4. The number of iterations we will apply before we get a number that is smaller than 4 is <= $LOG_2(N)$(because we divide by a number which is larger than 2 each time),while for N<4 the number of iterations is constant (Actually it is 1 ) and and we can ignore it for sufficiently large N.

So,it means we have O(LogN) as an upper bound.

So,the exercise from the book is solved. But,just out of curiosity,I'm interested more in some method to solve the equation and to get the exact solution. I'm not sure we can replace the difference equation with the differential equation here.