In Asymptotic Analysis of Algorithms, I'm seeing people say stuff like the following:
$$ T(n) = c + T( \lfloor \frac{3}{4} n \rfloor ) \in \theta( log_2 (n) ) $$
My understanding is that the recursion will occur $log_{3 /4 } ( \frac{1}{n} )$ times.
vis.
Recursion will terminate when: $$ \left( \frac{3}{4} \right)^i n = 1 \\ \left( \frac{3}{4} \right)^i = \frac{1}{n} \\ log_{3 /4 } \left( \frac{1}{n} \right) = i $$
Isn't it the case that $log_{3 /4 } ( \frac{1}{n} ) \in \theta \left[ - log_2 (n) \right]$ but $log_{3 /4 } ( \frac{1}{n} ) \not\in \theta \left[ log_2 (n) \right]$ ?
No, $\log_{3/4}(\frac{1}{n})$ will always be positive for $n > 1$, but $-\log_2(n)$ will always be negative. $\log_{3/4}(\frac{1}{n}) = \log_{4/3}(n)$, which is of order $\log_2(n)$.