complexity-theory Definition Memory Requirement Given a program and an input , the memory requirement of on is defined as the number of bits required in memory for the execution of on .