Where one can learn CS in very rigorous way? I'm interested both mathematics and computer science. I like math because one can formalize it rigorously and I have seen that many things can be defined by sets. Is there similar thing in computer science, as for example asymptotic notation is sometimes defined in very odd way, see https://math.stackexchange.com/questions/2731290/how-one-can-define-rigorously-the-time-and-space-complexities-of-algorithms ? I'm looking way to learn CS in a very rigorous way.
Be careful of what you wish for. Assuming you want rigorous self study, I'll recommend a few books. They are fairly old, but are classics. 

The Art of Computer Programming. Knuth is a mathematician at heart. The link is to the boxed set, but you can buy individual volumes. 

Elements of the Theory of Computation. This is as rigorous as you want to be and addresses directly the question of run-time bounds of various sorts. 

Similar is

Introduction to the Theory of Computation by Sipser

A somewhat different view of computation is found in

Structure and Interpretation of Computer Programs: A classic introduction to functional programming in Scheme - yet quite deep. 

For what it's worth, I have a doctorate in Mathematics and taught CS for over 40 years.