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.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
2
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
