-1

I am trying to show that for $a \sqrt{\frac{\pi }{k}}>1$, and $k \geq 1$, $$\sqrt{k (k-1)} \sqrt{\log \left(a \sqrt{\frac{\pi }{k}}\right)} = O(k)$$ using the standard big O notation. I can see that the function is beneath a straight line of a gradient of my choice, but how can I prove this? I cannot seem to conclude without getting rid of the $\log(\sqrt{1/k})$.

apg
  • 2,797
  • 2
    If $k> a^2 \pi$ then $0 <a \sqrt{\frac{\pi }{k}} < 1$ so $\log \left(a \sqrt{\frac{\pi }{k}}\right) < 0$ and $\sqrt{k (k-1)} \sqrt{\log \left(a \sqrt{\frac{\pi }{k}}\right)}$ is not a real number. – Henry Jan 02 '21 at 22:30
  • When you say "large $a$" do you mean "large $k$"? – Qiaochu Yuan Jan 02 '21 at 22:31
  • I mean, one may assume a is arbitrarily large. Also, $a \sqrt{\pi/k} > 1$. I edited the question. – apg Jan 02 '21 at 22:31
  • As $a\sqrt{\frac{\pi }{k} }\to 0$ then $\log$ is negative. How you can keep $a \sqrt{\frac{\pi }{k}}>1$ for constant $a$? – zkutch Jan 02 '21 at 22:37
  • The idea is $a$ is big enough to stop that. – apg Jan 02 '21 at 22:38
  • 2
    This can be if only $a = a(k)$ is not constant. And if it is function, then order depends on it. – zkutch Jan 02 '21 at 22:39
  • 1
    Is the implied constant in the big-$O$ notation allowed to depend on $a$? If so then it's very easy: as a function of $k$, $\log \left( a \sqrt{\frac{\pi}{k}} \right)$ is decreasing and so $O(1)$. But it seems strange to allow $a$ to be arbitrarily large while also ignoring its effect on the asymptotics. It's more accurate to say that the expression is $O(k \sqrt{\log a})$; here the implied constant is really a constant and for $k \ge 4$ can be taken to be $1$. – Qiaochu Yuan Jan 02 '21 at 22:40
  • Can one say that "this function grows at most linearly with $k$", given we can have $a \to \infty$? – apg Jan 02 '21 at 22:42
  • 1
    Again, it's strange to say that $a$ can be arbitrarily large while ignoring its effect on the asymptotics, because it's not possible to take $k$ to be arbitrarily large without making $a$ arbitrarily large (in fact $a$ must be $\Omega(\sqrt{k})$). What do you need this estimate for? I can't imagine an application in which you can ignore the effect of $a$ while it is changing. – Qiaochu Yuan Jan 02 '21 at 22:43
  • 1
    If we take such function $a(k) \geqslant C\sqrt{k}$, for which $\log$ is bounded, then you obtain needed. – zkutch Jan 02 '21 at 22:50

1 Answers1

1

Considering $a$ as function $a(k)>\sqrt{\frac{k }{\pi}}$ and taking $a(k)\to C>1,k\to \infty$ we obtain estimation $O(k)$.

For example $a(k)=\sqrt{\frac{k }{\pi}}\left(C+\frac{1 }{k}\right)$ for $C>1$.

zkutch
  • 13,410