-2
$\begingroup$

Can you help me find the theta complexity for lg(n^(1/2))?

$\endgroup$
1
  • $\begingroup$ $\Theta(\log n^{42})$. Also $\Theta(\log n^c)$ for any constant $c>0$ of your choice. $\endgroup$
    – Steven
    Jun 16 at 17:12

2 Answers 2

1
$\begingroup$

$log(n^{\frac{1}{2}}) = \frac{1}{2}log(n) = \theta(log(n))$.

More formally, there exists constants $c1$,$c2$ such that:

$c1⋅\frac{1}{2}log(n)≤log(n)≤c2⋅\frac{1}{2}log(n)$

$\endgroup$
0
$\begingroup$

A valid answer is

$$\lg(\sqrt n)=\Theta(\lg(\sqrt n)).$$

This is true as of $n=1$ with constants $1$.

Another valid answer is

$$\lg(\sqrt n)=\Theta\left(\sum_{k=1}^n\frac1k\right).$$

(Holds as of $n=2$ with constants $0.2$ and $1$.)

$\endgroup$

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