1. An execution time estimation method performed by an execution time estimation device which estimates an execution time of a program, comprising the steps, performed by the execution time estimation device, of: extracting, from the program, a plurality of partial programs which are obtained by partitioning the program using at least one of a conditional branch instruction and a function call instruction as a boundary point; calculating an execution time of each partial program and storing the calculated execution time in a storage section; storing a leading instruction and an end instruction of the each partial program, and the calculated execution time of each of the partial programs, in the storage section, such that the leading instruction, the end instruction, and the execution time are associated with each other; generating a branch history bit sequence which is a sequence of “True” and “False” on the conditional branch instruction if the program is executed, and storing the generated branch history bit sequence in the storage section; generating a partial program execution sequence in which an execution order of the partial programs is written, based on the branch history bit sequence; and adding up the execution times of the partial programs, based on the partial program execution sequence.