Program Performance

Program Performance

First of all Program Performance is divided into two sections: Space and Time. Due to the development of computer parts, the importance of space is gradually decreasing. So I focused more on time complexity in this lecture.

Space Complexity

Space complexity is defined as the amount of memory a program needs to run the completion. Back in the old days, our computer system had very limited space to run the program. Which occurred programmers need to study how to use the space efficiently. There is a funny example about this case.

Nowadays this single picture uses 106KB as a JPG image file. But this same game file was only 31KB. Which is even 3 times smaller than the picture below. This was the reason why space complexity got less important nowadays when we are making most of the program that runs on a computer.

Components of Program Space

Still, since we are learning about data structure space complexity is essential. Program space consists of instruction space, data space, and stack space. Instruction space is the compiler that generates the machine code itself. Data space is the component we use during programming. Many of us who used C in the first semester will be familiar with this concept. During solving questions in BOJ we choose the data type as large as possible to avoid errors. But using the smallest data type as possible is one of the easiest ways to make programs more space efficient. Stack space was not familiar but this was similar to the process of how the function was called when we start the program.

Time Complexity

Time complexity is the amount of computer time a program needs to run. It may be thought that the importance of time complexity has decreased as the computing power of computers has developed rapidly. However, as can be seen from the coding tests that are run these days, there are many cases where time complexity is limited. Also, the fast execution speed in the programs we usually use has a great influence on the user’s experience. When we measure time complexity there are three big methods: operation counts, step counts, and Asymptotic complexity.

Operation counts

One way to estimate the time complexity of a program or method is to select one or more operations, such as add, multiply, and compare, and to determine how many of each is done. The success of this method depends on our ability to identify the operations that contribute most to the time complexity.

Since Our class didn’t even started space complexity yet I’ll update this page next week after the class.