How Complex is Complexity?

This week we learned about complexity. Prior to learning about complexity, the name complexity itself would perhaps suggest that it is a complex subject (because who wouldn't want to explicitly state the difficulty of a particular topic in the subject name itself.) It turns out its focus is not to scare computer science students into thinking it is an extremely hard topic of the course, but it is actually to determine how complex certain functions are, ie their difficulty/efficiency.

In lecture, we wrote a function that was to return all the anagrams of a word, or a sequence of letters, since it didn't necessarily have to be a word itself. There were many approaches, some more efficient than others. One approach was to come up with all the permutations of the sequence of letters, and then see which permutations were actual words in the dictionary. This obviously is not very efficient considering the fact that if we had a sequence of letters that was 7 letters long, it would result in 5040 permutations. Imagine how long it would take for a sequence of letters longer than that. The other approach was the signature approach, which I thought was incredibly clever! The signature approach takes into account the fact that all anagrams have the same letters, so if the sequence was to be arranged in a specific way, it would be clear which words would be anagrams. So, as far as efficiency is concerned, this would be much better.

We know a function is more efficient than another function when its runtime is relatively shorter than that of another function. But there are other factors, such as the computer itself, and the compiler... Although I would have to ask what exactly a compiler is? It turns out that the compiler is the reason all our programming code actually works, the reason it actually produces any results. It is basically a program that takes a certain programming language, such as python, as input, and turns it into code that the computer's processor uses to actually process the code we typed up. If we wanted to see if a function is efficient or not, we would have to see how the function reacts as its input increases. We learned in lecture that step is defined as a computation that is done in a fixed amount of time. So then to determine a function's efficiency, we only need figure out how many steps a function takes according to its input size.

 Of all the subjects that we've learned so far in the course, complexity really challenges what we know. What I mean by that is, it is not just enough to be able to write code that works, you should write code that is efficient. This can often times prove to be quite challenging. So I guess complexity is complex afterall.