For ex: If I create a new Account, does salesforce algorithm always generate a new record Id or it looks for any of the old deleted record and assigns that Id?
No, new records always receive new IDs, and they are generally allocated in sequential order within the same transaction (but, not guaranteed, so do not depend on that behavior). The only exception to ID re-use are in sandboxes, where records copied to the sandbox will share the same ID as those in the production environment they came from. Multiple sandboxes, for example, can have the same record with the same ID. Newer records will always have an ID that is numerically higher than older records (where newer and older refer to the moment of the initial commit in the salesforce transaction lifecycle).
It's worth noting that some day, ID values might wrap around and we'd see ID reuse, as the ID key space is only 62^9 (13,537,086,546,263,552) values large, with the remaining six characters serving some other purpose (three for key prefix, and three for other purposes, mostly for pod identification so far). I don't think I've observed a single as large as 56,800,235,584 (six characters), so they're not even 1% of the way through their total space for a single key prefix. Of course, I can't see all ID values, such as deployments, etc, so it's possible some of them have exceeded those values, but not by too much, I'd assume.
It will always generate a new ID and will not reuse IDs from deleted records.