Every water heater has an altitude rating, sometimes printed right on the box. I don't think I ever saw a "regular" residential rated at less than 4000 feet. Some may be rated as high as 8 to 10 thousand feet. It also depends on your gas. Some high altitude areas, notably parts of Colorado, the natural gas is derated, so many appliances will operate without special adjustment.
If you call your local gas company, they will inform you of how things work in your area.