title: Solving recurrence: T(n)=sqrt(2)T(n/2)+log(n)
body: <p>Given the equation <code>T(n)=sqrt(2)T(n/2)+log(n)</code>.</p>
  
  <p>The solution points to case 1 of the M.T. with a complexity class of O(sqrt(n)). However after my understanding log(n) is polynomial greater then sqrt(n). Am I missing something?</p>
  
  <p>I used the definition as following: n^e = log_b(a) where a = sqrt(2) and b = 2. This would give me e = 1/2 &lt; 1. log n is obviously polynomial greater then n^e.</p>