There are three things that we have learned in this week that are really important (1). Input size. (All complexity functions are measured on input sizes hence you need figure out input sizes correctly.) (2). Input doesn't take memory when t is read-only. Memory (in the context of space complexity of an algorithm) refers to "additional" memory needed (3). I keep saying that C-programs are algorithms but actually this is not completely right. I say this only for those students who hate Turing ma- chines. Algorithms are Turing machines that halt on all inputs. Therefore If you are given an algorithm, you have many many C programs to imple- ment it; some are good some are bad. However, if I give you a C program, you usually don't have many drastically different "programs" to implement the C program (at most you use different compilers, but the assembly code you get is roughly the same.) Many people also think to make an algorithm any times faster (on almost l inputs! not just a single one, not necessarily al inputs) is a mystery (Blum's speedup theorem). Of course, if you can make it two times faster, you can make it any times faster. Now, let us look at an idea that makes an algorithm two times faster For a natural number represented in digits (so the size of input is logio T), we learned in our grammar school how to do arithmetic operations like addition, subtraction, multiplication, etc., on those digits. Being in digits, you are talking about alphabet 10, 1,2, ...,9). Because of this, we were taught to do those arithmetics digit-by-digit. Now, suppose that you do two digits a time. Hence, in order to multiply 1234 5678 you do this (12)(34) x (56)(78) and now your alphabet is {00,...991 (if we humans have 100 fingers to begin with, then we would do math in this way thousands years ago)you might have already noticed that the input size now is log100 r where r is the natural number mentioned at the beginning). This will make our multiplication at least two times faster. Can you figure it out and sketch how we would do this for n digit by n digit multiplication and why it is at least two times faster? This is why Blum's theorem works. There are three things that we have learned in this week that are really important (1). Input size. (All complexity functions are measured on input sizes hence you need figure out input sizes correctly.) (2). Input doesn't take memory when t is read-only. Memory (in the context of space complexity of an algorithm) refers to "additional" memory needed (3). I keep saying that C-programs are algorithms but actually this is not completely right. I say this only for those students who hate Turing ma- chines. Algorithms are Turing machines that halt on all inputs. Therefore If you are given an algorithm, you have many many C programs to imple- ment it; some are good some are bad. However, if I give you a C program, you usually don't have many drastically different "programs" to implement the C program (at most you use different compilers, but the assembly code you get is roughly the same.) Many people also think to make an algorithm any times faster (on almost l inputs! not just a single one, not necessarily al inputs) is a mystery (Blum's speedup theorem). Of course, if you can make it two times faster, you can make it any times faster. Now, let us look at an idea that makes an algorithm two times faster For a natural number represented in digits (so the size of input is logio T), we learned in our grammar school how to do arithmetic operations like addition, subtraction, multiplication, etc., on those digits. Being in digits, you are talking about alphabet 10, 1,2, ...,9). Because of this, we were taught to do those arithmetics digit-by-digit. Now, suppose that you do two digits a time. Hence, in order to multiply 1234 5678 you do this (12)(34) x (56)(78) and now your alphabet is {00,...991 (if we humans have 100 fingers to begin with, then we would do math in this way thousands years ago)you might have already noticed that the input size now is log100 r where r is the natural number mentioned at the beginning). This will make our multiplication at least two times faster. Can you figure it out and sketch how we would do this for n digit by n digit multiplication and why it is at least two times faster? This is why Blum's theorem works