"Dedicated server" + "cheap hosting" means you are renting a virtual server, not your own hardware. Fully dedicated hardware is usually many hundreds of dollars a month.
Virtual servers are fully accessible through the hypervisor / virtualization software, you will never know it happened, and they don't need a local account. Encryption won't help here as the keys are also accessible, and the encryption just announces that you have something to hide.
Co-lo ( co-location ) service providers will give you rack space for your hardware, with the condition that you, not them, are responsible for the hardware service. They will push the power button, but that's about all. If the RAM goes, you drive over to the data center and change it. They still have access to the hardware but they will have to pull the tools out to get to it.
Ultimately, your server's security is a balance between how important/unique your process is, how valuable it is to you, and how valuable it is to others. Generally, data center staff couldn't care less what you are doing until something like excessive bandwidth or a subpoena make them care.