I have one iPhone 4s 8GB version which I updated to iOS 9.3.5 and when I see the storage available, I got 4.2 GB after installing some apps. When I counted the sum total of storage consumed by all apps, it was only < 300 MB. But, it showed that the usage is 866 MB.
I tried hard resetting the phone, (Erase all content) and after restart, I selected Setup new iPhone (instead of restoring from backup). However, I have restored backup of WhatsApp from WhatsApp app itself.
The iCloud backup size of WhatsApp is also 5.1MB only and that of the entire phone is < 100MB only. I have gone through this post and did the same way, but still iOS available space doesn't add up and also from iPhone available space: significant difference between iTunes and iPhone but still, there is 500MB missing somewhere?
I don't currently have Windows OS/Mac to install iTunes, I use Linux Mint and iTunes doesn't detect iPhone in Wine (on Linux) and I also can't install VirtualBox due to some reasons.
If the solution to this problem requires iTunes, then I may need to install Windows.
Edit: I updated my iPhone from iOS 7.0 to 8.4.1 and then finally to 9.3.5. After that I erased all its contents. Are the iOS downlodaed installation files still there on my iPhone?