\renewcommand\arraystretch{1.3}
  \begin{array}[t]{l|l|l|l}
\index{OBDD!running time of algorithms!upper bounds}
  \hbox{Algorithm} & \hbox{Input OBDD(s)} & \hbox{Output OBDD} &
\hbox{Time-complexity} \\\hline
  \reduce          & \hbox{$B$} &
  \hbox{reduced $B$} & O(|B|\cdot \log |B|) \\
  \apply           & \hbox{$B_f$, $B_g$ (reduced)}           &
  \hbox{$B_{f\;{\rm op}\; g}$ (reduced)} & O(|B_f|\cdot |B_g|)\\
  \restrict        & \hbox{$B_f$ (reduced)}       &
  \hbox{$B_{f[0/x]}$ or $B_{f[1/x]}$ (reduced)}  & O(|B_f|\cdot \log
|B_f|)\\
  \exists           & \hbox{$B_f$ (reduced)} & \hbox{$B_
  {\exists x_1.\exists x_2.\dots \exists x_n.f}$ (reduced)}   &
\hbox{NP-complete}\\
    \end{array}