We come across the problem of inverting a function often in computer science. Instead of solving it by brute force, sometimes it would be much easier to do it with the help of Θ(⋅)\Theta( \cdot ), if we only care about the asymptotic trend. See two examples below.

  1. If tln⁡t=nt \ln t = n, then t=Θ(n/ln⁡n)t = \Theta( n / \ln n ).
ln⁡t+ln⁡ln⁡t=ln⁡n  ⟹  ln⁡t=Θ(ln⁡n)  ⟹  tΘ(ln⁡n)=n  ⟹  t=Θ(nln⁡n) \begin{aligned} &\ln t + \ln \ln t = \ln n \\ \implies &\ln t = \Theta( \ln n) \\ \implies &t \Theta (\ln n) = n \\ \implies &t = \Theta \left( \frac{n}{\ln n} \right) \end{aligned}
  1. If t2ln⁡t=n3t^2 \ln t = n^3, then t=Θ(n/ln⁡n)t = \Theta( n / \ln n ).
2ln⁡t+ln⁡ln⁡t=3ln⁡n  ⟹  ln⁡t=Θ(ln⁡n)  ⟹  t2Θ(ln⁡n)=n3  ⟹  t2=Θ(n3ln⁡n)  ⟹  t=Θ(n3ln⁡n) \begin{aligned} &2\ln t + \ln \ln t = 3\ln n \\ \implies &\ln t = \Theta( \ln n) \\ \implies &t^2 \Theta (\ln n) = n^3 \\ \implies &t^2 = \Theta \left( \frac{n^3}{\ln n} \right) \\ \implies &t = \Theta \left( \sqrt \frac{n^3 }{\ln n} \right) \end{aligned}

Application

Suppose there is an algorithm that has running time O(n3/t)+O(tlog⁡t)O(n^3 / t) + O(t \log t), for any t>0t > 0. We want to choose a tt that minimizes the asymptotic time complexity of the algorithm.

As for any a,b>0a, b > 0,

max⁡{a,b}≤a+b≤2⋅max⁡{a,b}. \max \{a, b \} \le a + b \le 2 \cdot \max\{ a, b \}.

It suffices to choose a tt that minimizes max⁡{n3/t,tlog⁡t}\max\{ n^3 / t, t \log t\}. By the result of previous section, we can choose

t=Θ(n3log⁡n), t = \Theta \left( \sqrt \frac{n^3}{\log n} \right),

and the time complexity is

O(n3log⁡n). O(\sqrt{n^3 \log n}).

Reference

[1]. Ryan O'Donnell, Lecture 2, CS Theory Toolkit, CARNEGIE MELLON UNIVERSITY