I don't see what you are getting at. Time is linear, how can a story not be linear? Do you mean non-branching?
Deus Ex, is actually 100% linear.
...
(GTA)
Then go and do the story mission. It will be the same mission. The dialogue will not have changed. Nobody will mention how you look like the guy who killed 100000 of their buddies.
In Deus Ex, the Dialog does change based on your actions. NPCs will mention that you have been brutal. You can kill characters, thus turning other characters against you.
Can you describe what a non-linear story would be? Maybe the developer designs each level based on what you did in the last? That would be pretty expensive.
This comment was edited on Oct 15, 01:13.