About a month ago I began receiving messages on my iPhone 6 that I was close to my storage capacity despite not having many pics or apps on the phone. When I checked my storage capacity under "Usage", it said I still had about half my storage. The problem has become progressively worse and now I am totally out of storage despite deleting ALL of my pics and vids and many of my apps. Now under "Usage", it says I have 0 bytes available even though I've only been deleting and adding nothing. Even when I plug the phone into my PC, it says I can't sync because there's not enough storage even though I just did so a few hours ago with no problem. I should point out that I am not on the cloud at all.
In addition, apps (including my e-mail) are starting to open and close immediately. In the past 2 days, it seems like the entire phone is crashing.
The only solutions I've heard are to restart my iPhone (which didn't work), or to upgrade to iOS 9.3.5 (which I don't have the storage capacity to do). Any suggestions would be greatly appreciated. Thank you.