See, that's a non-linear story, but it's not an open world. You still only have the one mission, and your impact never carries from one mission to the next.
I attempted to design a death note game some time back, and for all intents and purposes it is a semi-non-linear open world game, and the reason I can't work on it is how staggering creating that was. Essentially you could lose in any mission, or shoot yourself in the foot for a mistake you made near the start, and the end was dependent on all of the variables in the entire game. I knew the options and story, but keeping track of it all was like writing 100 different games at once. It was like Mass Effect, but the ending actually mattered
Like I said, it could be done, but the effort you put in wouldn't work in respect to the result you get.
In a linear game you just make the one path, in a non-linear game you have to make every path, which means more work per hour of gameplay.
Perhaps, and this is a stretch, a game could be made that
generates events and missions based on previous actions. The technology exists to do this, and it would be much easier to do (for a very skilled team, mind) the only problem is whether the plot would still be involving. It could end up feeling cut and pasted, where you do virtually the exact same mission, or see the same cutscene, or have the same dialogue, and the names and places have changed as if someone has madlibbed you previous exploits.
OR, it could be a small open world. If it's small, it's easier to do. Basically, the less impact the player can have, the less you need to make the world react, and so the easier it is to do.
It might be a better idea to design a smallish world, and then think of how to make it non linear and open, but still engaging. Keep with the detective thing maybe, but have multiple cases. Track how many cases are successful. Unsuccessful cases might come back later. Have the chance of a certain character experiencing a crime be tracked by a variable, but every character could die. This could be a world where the 'main' villain is killed off in act II by some random mugger, and you spend most of a quest just going "holy fuck, this guy was evil, good thing he got stabbed for a rolex"
Again, it would have to be 'madlib' style missions, where names and motives and weapons are swapped out, but you'll often be feeling like you've done it all before.
Basically, difficult, not impossible. Build a world, then address whether it would be possible or not, and to what degree. You'll never get perfect open non-linearity, but you can approach it.