Complexity

This week a new topic was started, it was a topic which was covered moderately in CSC108 and it is complexity and run-times. Complex is a method of classification of programs based on the amount of steps it takes to complete a program depending on the amount of information that it process. The motivation for this concept is clear, as the complexity of a program is directly related with its performance, thus in order to modify or improve a program to make it more efficient, it is necessary to understand the level of complexity of the code. For example, in assignment one, to execute the recursive code to find the smallest number of moves, the complexity is O(n!),  and in class we were told that some students were able to solve the minimum number of moves for moving 1000 cheeses in a matter of seconds, while it takes me a full minute to find the minimum of 20 moves. Thus, modifying the algorithm that repeatedly runs in a code can greatly improve the performance. But how is the program's performance quantitified? The way to do this is by running time analysis, which puts the running time as a function of the size of the input for a specific program  and it can range for code that are constant for all inputs like appending to list to code that grows logarithmically like a binary search tree. The prof then went on to compare linear search and binary search, and various sorting methods to contrast the amount of time that algorithms of different complexity take to do the same problems. These difference the prof demonstrated in class sparked my interest in learn more about how to implement code with various complexities; it serves as a reminder that I should always keep the concept of efficiency in mind while programming and try to reduce the running time of accomplishing the goal of a function as small as possible.