For slide 43 of 61 in the solution review, can you please explain the last step in the simplification of 2^(ceil(log_2(n))-1? From my understanding of the properties of logarithms of exponents 2^(log_2(n)) should simplify to n. Why does 2^(ceil(log_2(n))-1 simplify to 2(n - 1) - 1?
2 Likes
Hi @Matt_O_Hanlon!
The slide says 2^ceil(log_2(n)) - 1 <= 2(n - 1) - 1.
Note the use of <= instead of =. Hope this helps!
I see that the in depth explanation says that it is at least n-1, which works with the simplification of (2^log_2(n)) - 1 simplifying to n - 1, but since that’s the best case, and we’re looking for worst case, that isn’t the information we need. I don’t think OP or myself see how the slides or even the in depth explanation, are making the logical leap to how 2^(ceil(log_2(n))-1= 2(n - 1) - 1= 2n - 3. Can we get more information on this?
I also don’t understand, in the explanation, where the 2^(i) + 1 comes from. This is the section I’m referencing:
The number of iterations of the inner loop changes on integer powers of 2, as you would expect with the ⌈n⌉ exponent. At n = 4, the number of iteration is 3, at n = 8, it is 7 etc. So, on values of n that are integer powers of 2, the number of iterations is n - 1. That conforms to our lower bound on the number of iterations.
The upper bound is evident on n = 2^i + 1, where i = 1, 2, 3, 4, …, i.e., n = 3, 5, 9, 17, … You will notice that at at these values of n, the number of iterations of the inner loop is one less than the next higher integer power of 2, i.e., 2(n - 1) - 1 = 2n - 3.
Edit: Another question I have is that if this were asked during an interview, would writing out the loop iteration values respective to n be the way to determine this inner loop run time, or is there a formula that explains this?
1 Like
Hi Hafsa
Thank you for taking the time to answer my question. Unfortunately, that doesn’t help me. I can certainly understand that 2^ceil(log_2(n)) - 1 <= 2(n - 1) - 1, but where or how do we find 2(n-1)-1?
Hi Matt,
This one confused me too! It tripped me up because the expression 2^i + 1 results in a single integer value, but I think what they authors were actually referring to a range of values (ie [2^i + 1, 2^2i - 1]). So, the explanation could read something like
Blockquote
…on values of n that are integer powers of 2, the number of iterations isn - 1. …
For values of n that range from[2^i + 1, 2^2i - 1], i.e., n = 3, 5, 9-15, 17-31, … the number of iterations will be2(n - 1) - 1 = 2n - 3.
I hope that helps!
Hey Matt,
So I see now about how the range is there, but I don’t think anyone has really answered where we’re finding the 2(n-1) - 1, at least not in the sense of their explanation in slide 43 where they just magically come up with 2^(ceil(log_2(n))-1<= 2(n - 1) - 1<= 2n - 3. As we both know, 2^(ceil(log_2(n)) with the rules of logs simplifies to n, which is how we’re getting the sum being at least n - 1, but I don’t see how, without the very in depth work to figure out the pattern to determine that it’s 2(n-1) - 1 for the upper bound because we drew out that table to see the pattern (which seems like it could be unreasonable for an interview, but someone please correct me if I’m wrong), how did we make the logical leap to this in the slides anyways? I guess my main sticking point is that I think the slide explanation makes it appear that 2^(ceil(log_2(n))-1 is some how then transforming into 2(n-1)-1, when really, we used 2^(ceil(log_2(n))-1 to find the lower bound, and then we went a completely different direction to figure out 2(n-1)-1 as the upper bound because then we said, yes, obviously, the lower bound would be lower than the upper bound of the values in the loop, so then 2^(ceil(log_2(n))-1 <= 2(n-1)-1 <= 2n-3.
Just seems like something that could’ve been better explained with a video in this case. Normally, I’m a fan of sticking to reading when possible, but I think it was just detrimental in this case as it led to much more confusion for me.
Thanks for the help Matt. Maybe my explanation will help clarify some things as well, but seems like we both eventually understood their explanation.
1 Like