Prove 2^sqrt(log(n))= O(n^a)
- by user1830621
I posted a question similar to this earlier, although it seemed like it was much easier.
I know the underlying principle of Big-O notation says that to prove that 2^sqrt(log(n)) is O(n^a), there must exist a positive value c for which c(n^a) = 2^sqrt(log(n)) for all values n = N.
c*n^a >= 2^sqrt(log(n))
c >= 2^sqrt(log(n)) / n^a
This number will always be positive so long as n 0. I suppose I could make N = 1 just to be safe.
c = 2^sqrt(log(n)) / n^a
N = 1
c*n^a = 2^sqrt(log(n) <= 2^log(n) for all values of n >= 1
Now, I know this is incorrect, because I could just as easily claim that the function 2^sqrt(log(n)) is O(n)...