A still-very-common use case for spreadsheets is just to manage lists of things. For these, there are no formulas or dependencies at all. Another is simple totals of columns of numbers.

There are many common spreadsheet use cases that don't involve complicated dependency trees.

It's a common CPU vs RAM decision to make. Dependency graph consumes memory, while recalculating everything for a number of iterations could happen on stack one formula at a time in a loop. On 6502 it mattered. On modern CPUs, even with RAM crisis I'm sure for 99.9% of spreadsheets any options is good enough. Say, you have 10K rows and 100 columns - it's 1M calculations to make.

Keeping a dependency tree is not complicated