O(n)だね。
文字列変換時にBCDにするのではなく演算からBCDとして扱うプログラムを見たことある。
あまり効率が良いとは思えなかったが。