Default [Q] How does Google Navigation work? Does it depend on GPS or cellular network?

How does Google Navigation work? Does it depend on GPS or cellular network or both?

I have a Tmobile Note 3 and sometimes, when my mobile data is showing "E" the Google Maps app can't even get a GPS lock?

Is it the phone? Do I have a lemon?

My friend has a Galaxy Note 3 on Verizon and her Google Maps worked just fine. Her data was showing 4G LTE.

Is anyone here an expert on how Google Maps works? I thought it only needed GPS? I tried all the different GPS settings ("full", power save, GPS only, etc) and none of them made any difference.