In more temperate climates (forests, jungles, etc.) burying feces is preferred as it will be broken up by microbes in the soil while being somewhat protected from the environment. Plant growth in these areas is also rapid enough that cut roots are generally a non-issue. (I'm assuming you aren't hacking through larger roots.) In general the warmer the climate the better the decomposition.
Deserts, canyons, and alpine areas above treeline represent special cases; there is generally a lack of organic soil in which to bury waste and vegetation grows very slowly, if at all. In such areas, particularly heavily impacted ones, packing out waste via WAG bags is preferred and sometimes legally mandated.
On rarely-visited routes in the high alpine there are two other options which are sometimes used: the first method is to go on a rock then toss it down a moraine or crevasse. The second is to smear it into a paper-thin layer on a rock facing the sun; the sun and wind will slowly bake and abrade it away. (It's worth noting that the Leave No Trace Center for Outdoor Ethics found most people don't spread it thin enough.)
Regarding toilet paper, many advocate packing it out. I've heard differing opinions on how well it decomposes in the wild, and often that's climate dependent. Outside of areas with good organic soil I would pack it out. Another option that many use is to skip toilet paper and use snow, rocks, or leaves instead.