L(2,1)-labeling is a graph coloring model inspired by a frequency assignment in telecommunication. It asks for such a labeling of vertices with nonnegative integers that adjacent vertices get labels that differ by at least 2 and vertices in distance 2 get different labels. It is known that for any k >= 4 it is NP-complete to determine if a graph has a L(2,1)-labeling with no label greater than k. In this paper we present a new bound on complexity of an algorithm for finding an optimal L(2,1)-labeling (i.e. an L(2,1)-labeling in which the largest label is the least possible). We improve the upper complexity bound of the algorithm from O^@?(3.5616^n) to O^@?(3.2361^n). Moreover, we establish a lower complexity bound of the presented algorithm, which is @W^@?(3.0739^n).