In many engineering and meteorological applications, atmospheric turbulence within the planetary boundary layer is described in terms of its representative parameters. One such parameter is the structure-function (or structure) parameter that is used to characterize the intensity of turbulent fluctuations of atmospheric flow variables. Structure parameters are derivatives of structure functions, but are used more frequently than the latter ones for practical needs as they do not explicitly include dependence on the separation distance. The structure parameter of potential temperature, which is the subject of this study, describes the spatial variability of the temperature fluctuations. It is broadly represented in theories and models of electromagnetic and acoustic wave propagation in the atmosphere, and forms the basis for the scintillometer measurement concept. The authors consider three methods to compute the potential temperature structure function and structure parameter: the direct method, the true spectral method, and the conventional spectral method. Each method is tested on high-resolution potential temperature datasets generated from large-eddy simulations of a variety of convective boundary layer flow cases reproduced by two representative numerical codes. Results indicate that the popular conventional spectral method routinely exaggerates the potential temperature structure-function parameter, likely due to the unrealistic assumptions underlying the method. The direct method and true spectral method are recommended as the more suitable approaches.