We study operator complexity on various time scales with emphasis on those much larger than the scrambling period. We use, for systems with a large but finite number of degrees of freedom, the notion of K-complexity employed in arXiv:1812.08657 for infinite systems. We present evidence that K-complexity of ETH operators has indeed the character associated with the bulk time evolution of extremal volumes and actions. Namely, after a period of exponential growth during the scrambling period the K-complexity increases only linearly with time for exponentially long times in terms of the entropy, and it eventually saturates at a constant value also exponential in terms of the entropy. This constant value depends on the Hamiltonian and the operator but not on any extrinsic tolerance parameter. Thus K-complexity deserves to be an entry in the AdS/CFT dictionary. Invoking a concept of K-entropy and some numerical examples we also discuss the extent to which the long period of linear complexity growth entails an efficient randomization of operators.