Any suggestions for A Proof-of-Work algorithm in literature so that the time required for solving it is linear with the puzzle difficulty ??
I don't think an algorithm like that would exist. For PoW to facilitate a random slot leader for block generation, it has to be necessary that the PoW puzzle is really hard to solve by anyone and that no deterministic polynomial time algorithms exist which promise a solution to that puzzle, because if they would then I think that a person with a faster rig and a faster processor would solve the PoW puzzle the fastest and become the slot leader every time.
Since I have already stated that there shouldn't exist any deterministic algorithm to solve the puzzle in polynomial time, this means that the best that anyone contending for becoming the slot leader can do is to try the probabilistic approach and wish that their random nonce solves the puzzle faster than anyone else.
It is just because of this randomized (probabilistic) nature of the solution to the puzzle that the very slot leader elected is random in nature.
If you know about complexity classes of P and NP, then you will realize that if PoW is linearly solvable then it lies in P, whereas it should lie in NP i.e. given an oracle which takes all the correct steps and makes all the correct choices (meaning that selects the random nonce correctly every time) every time, then the problem is polynomial time. This means that given a solution, you can verify that the nonce is correct in polynomial time but you cannot solve the puzzle in polynomial time.