To fairly assess the performance of battery state of charge estimation algorithms, a standardized evaluation method is required. This paper expands on a previously proposed evaluation method by including a measurement of computational complexity. Since traditional complexity metrics, such as computation time, may vary across devices and over time, this paper proposes a specialized metric to categorize computational complexity: approximate operational effort (AOE). AOE is determined by running the algorithm and a standard mathematical and memory operation on a device such as a PC and normalizing run time based on these operations. AOE is measured on three different devices for four algorithms, and is shown to decrease the variability between devices from a factor of ten to less than four, which is sufficient to differentiate algorithm performance across devices. The algorithms are also deployed to a microcontroller to compare with the PC based complexity measurement.