apt-get autoremove is very conservative, which results in the behaviour you’re seeing. While
apt-get install only considers direct dependencies and recommendations by default,
apt-get autoremove also considers suggestions (very weak dependencies). This is asymmetric and means that by default,
apt-get autoremove won’t necessarily fully undo a package installation.
Thus in your case, installing
checkinstall pulled in a number of packages, all of which end up somehow considered non-removable by
apt-get autoremove; for example,
build-essential is kept because
apt (which is definitely necessary) suggests
dpkg-dev, which recommends
build-essential. You’ll find relationships of this kind for every package pulled in by
To fix this, you can add
Apt::AutoRemove::SuggestsImportant "false" ;
With this setting,
apt-get autoremove will find more packages to remove. Since your system is newly installed, it should be safe (by that I mean that the asymmetry mentioned above won’t cause many surprises, because you haven’t installed many packages); but do examine the list of packages it’s going to remove before actually removing them!