Memory systems that can predict a physical address associated with a logical address, and methods for use therewith, are described herein. In one aspect, the memory system predicts a physical address for a logical address that follows a sequence of random logical addresses. The predicted physical address could be a physical location where the data for the logical address is predicted to be stored. In some cases, the host data can be returned without accessing a management table. The predicted physical address is not required to be the location of the data to be returned to the host for the logical address. In one aspect, the memory system predicts a physical address at which information is stored that may be used to ultimately provide the data for the logical address, such as a location in the management table.