In a map that is built from tiles, I have given a fairly full explanation of the approach I've found to work best down on the low end devices:
How should I represent a tile in OpenGL-esHow should I represent a tile in OpenGL-es
Memory is the memory used by the tiles (not how many times they are reused) and the relatively small amount of memory used to index where to place each tile.
Maps like Terraria are entirely possible!