In embedded devices, like PDAs, limited battery power presents a bottleneck while running power-hungry applications. Hence, it is important for such applications to be energy aware. Consider a scenario where the embedded device is wirelessly linked to a tethered server and can exploit the computing cycles in it. This presents an opportunity to execute parts of an application remotely and reduce computing energy on the embedded device. However, such a scheme is limited by the transmission energy needed in transferring program parts to be executed remotely. In this paper, we present a fast profile-guided partitioning algorithm that can choose the program parts that can be executed remotely and save energy on the embedded device. We also discuss an optimal version of the partitioning algorithm, also based on profiles, that can maximize the energy savings on the embedded device. However the optimal algorithm has a large time and space complexity and hence needs a lot of energy to execute. We argue that the partitioning might have to be done on the client device more than once and hence the need for a fast algorithm that does not consume too much energy by itself. We have chosen Java programs in particular because of their widespread use in embedded applications. We treat Java objects as the program parts that could be considered for remote execution. Our algorithm can, in general, be applied to programs written in any Object-Oriented language. Experiments show that our approach can conserve energy in embedded devices from 29% to 43%. We also present results comparing the fast algorithm with the optimal one.