In this paper we derive analytical upper bounds on the covariance of the state estimates in SLAM. The analysis is based on a novel formulation of the SLAM problem, which enables the simultaneous estimation of the landmark coordinates with respect to a robot-centered frame (relative map), as well as with respect to a fixed global frame (absolute map). A study of the properties of the covariance matrix in this formulation yields analytical upper bounds for the uncertainty of both map representations. Moreover, by employing results from Least Squares estimation theory, the guaranteed accuracy of the robot pose estimates is derived as a function of the accuracy of the robot's sensors and of the properties of the map. Contrary to previous approaches, the method presented here makes no assumptions about the availability of a sensor measuring the absolute orientation of the robot. The theoretical analysis is validated by simulation results and real-world experiments.