Extracted text: 1. In each row, four items are given: function to which runtime is proportional, original input size, original runtime, new input size. You'll fill in the expected new runtime. Refer to Runtime Rules of Thumb to figure out the answers. Original Runtime Original Runtime New Input Size New Runtime in ms proportional to input size in ms logn 1,000 4 1,000,000 nlogn 20 4 400 n 1,000,000 2,000,000 4 n 3,000,000 9,000,000 4 3,000,000 4 6,000,000 1000 4 4000 20 4 180 12,000 4 36,000 1 1,000 4. 1,000,000 2 100 4 101 n! 100 4. 101 n" 100 101 4,