If $j \in Z^+$ and $k \in R^+$ and $j − 1 < \log k < j$. Why is $j = O(\log k)$? (All log's are in base 2)

I know I have to find constants where $j <= c \cdot \log k$ but I need some help with it.


You solved your own question. Quite literally the bounds you gave (with $c=1$ or $c=2$) should suffice

  • $\begingroup$ I guess my question is that you can also find constants for j >= c.logk and therefore j must be theta(logk) but it shouldn't be. $\endgroup$ – cuffty Jul 19 '20 at 16:37
  • $\begingroup$ Given the restrictions you have described, it is indeed theta of log(k). If you got to those constraints while solving something, and you are sure that j shouldnt be theta of log(k), then try to post the full question - you might have had some problem in your solution beforehand $\endgroup$ – nir shahar Jul 19 '20 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.