educative.io

How are we calculating 2^(ceil(log_2(n)))

Courses
,
#1

How we came to the value - 2^(ceil(log_2(n)))? Can anyone help me understand this?

Type your question above this line.

Course: https://www.educative.io/collection/5642554087309312/5634727314718720
Lesson: https://www.educative.io/collection/page/5642554087309312/5634727314718720/5705431468998656

1 Like
#2

Hello @Sumit_Dwivedi,

Basically, 2^(ceil(log_2(n))) is the time complexity of the inner loop that is a for loop.

  1. We have two variables that are responsible for the iterations of the loops are var and n.
  2. We calculate it by assuming the n = 16 when the var and n are equal. The outer loop that is while stops.
  3. The total iteration of inner for loop will be 2^(k+1)-1, and to find the total iterations of for loop, we have to find the value of k.
  4. We know that the last value of var has to be less than n, so 2^k has to be less than n too, i.e., 2^k < n.
  5. We can now apply the log_2 function to both sides such as log_2(2^k) < log_2(n).
  6. By this k is in O(log_2(n)). Also k = floor(log_2 (n))
  7. Let’s put the value of k back into this expression 2^(k+1)-1.
  8. By putting we get 2^(floor(log_2(n))+1)-1.
  9. That is equal to 2^(ceil(log_2(n))-1.

I hope I have answered your query; please let me know if you still have any confusion.

Thank You :blush:

#3

Hi, I am still not able to understand this - The total iteration of inner for loop will be 2^(k+1)-1. How are we calculating this total iteration?