Is $\mathcal{O}(3^{n/2})$ equal to $\mathcal{O}(3^n)$? I am not sure how the growth of exponentials with fractions.
Asked
Active
Viewed 53 times
-1
-
MathJax hint: enclose multicharacter exponents in braces, so 3^{(n/2)} will give $3^{(n/2)}$. The stuff in braces gets treated as a unit. It works for fractions, subscripts, etc. – Ross Millikan Nov 28 '17 at 03:56
-
Ok, trying to edit on my phone, thanks – LuxuryWaffles Nov 28 '17 at 03:57
-
1Your title and body ask slightly different questions: do you mean $2^n$ or $3^n$? – Noah Schweber Nov 28 '17 at 04:00
1 Answers
2
Remember that $a^{b\cdot c}=(a^b)^c$. So e.g. $3^{n\over 2}=3^{n\cdot{1\over 2}}=(3^{1\over 2})^n$.
Now if $0<u<v$, what do you know about the growth rates of $u^n$ versus $v^n$?
Noah Schweber
- 245,398
-
So this means if simplified, it would be O 2^n = O 1.7^n? So 2 grows slower than 3^1/2? – LuxuryWaffles Nov 28 '17 at 04:03
-
@BloopieBloops I don't understand that comment at all. How are you assuming $\mathcal{O}(2^n)=\mathcal{O}(1.7^n)$? And what do you mean by "$2$ grows slower than $3^{1\over 2}$"? – Noah Schweber Nov 28 '17 at 04:07
-
I meant i can say that 3^(n/2) = O (2^n) right? Or 2^n = Ω (3^(n/2)) – LuxuryWaffles Nov 28 '17 at 04:49