Maybe it would be possible to give a somewhat useful first answer just as a post here; I'll try.
Going way back in computing, often an important issue was, how fast will a program run? That study is now sometimes called computational time complexity.
This study was important because, for some common work, some ways of programming the work ran many times faster than some other ways -- i.e., the study of computational time complexity got some big results.
Usually in practice an issue of a little less concern than running time was how much of the computer main memory would a program need, and this study was computational space complexity.
The first big case of big gains was running time for sorting. So, for some positive integer n, we are given n numbers (or alphabetic names, etc.) and want to sort them into ascending order. So, an obvious first approach is to look at all n numbers one at a time and find the smallest. Then look at the remaining n - 1 numbers and again find the smallest. Then with a little algebra, the running time grows proportional to n^2 (n times n, n squared). So we say (I'm omitting some fine points) that the running time is "big O n^2" written
O(n^2).
Now for some big stuff: (1) There is a way (method, technique, algorithm) called heap sort with running time (computational time complexity)
O(n log(n) )
both on average for random numbers and also for the worst case of the order of the given n numbers. (2) Heap sort works by comparing numbers two at a time (so did our
O(n^2)
algorithm above), and there is a cute counting result from A. Gleason, long a math prof at Harvard, that shows that for sorting by comparing numbers two at a time
O(n log(n) )
is the fastest possible. (3) Heap sort is also in-place which means that the storage used, except for a constant independent of n, is just what is needed for the n numbers being sorted.
After sorting, there was interest in working with trees. Likely the tree most people are most familiar with is the hierarchical file system. A tree can be good for keeping a set of numbers in order while adding numbers to the set or removing numbers from the set. To get good guaranteed fast running time, we want the tree balanced, that is, all the paths in the tree from the root to the leaves are about the same length. So, keeping the tree balanced while making the changes and doing so with relatively fast worst case running time was a challenge. One solution was AVL trees (see D. Knuth's The Art of Computer Programming: Sorting and Searching or more recent books listed in this thread) and, mostly for data stored on disk, B-trees. Actually there are several important, that is, relatively fast, algorithms for manipulating trees.
Early on in computing there were more problems with algorithms that improved running time, e.g., string searching.
There is a general technique, dynamic programming, that is the basis of several important, relatively fast algorithms. Here the programming is in the sense of the English project planning, that is, from the field of optimization in operations research.
Generally, given a program, it can be difficult to do algebraic manipulations, say, assuming either random or worst case inputs, to find the "Big O" running time. Knuth's book starts with a lot of algebraic techniques that can help finding Big O running times. That work can be as challenging as we please.
There is some work that early on was not really in computer science but very much needs computers and where running time was and is a huge issue. An important source of such work was optimization in operations research. The first work of concern was the simplex algorithm of linear programming. Next was the closely related integer linear programming, i.e., combinatorial optimization. There were too many cases of problems starting with n numbers and running in
O(2^n)
which is exponential and so bad that, for too many realistic problems, we could run for billions of years with about the fastest computers we can imagine and big enough to fill the visible universe, literally.
So, a question became, can we have some positive integer k and have worst case running time grow only as
O(n^k)
that is, a polynomial in k? The problem was generalized and now is the question of P versus NP, the leading question in computational complexity and maybe in much of computer science and pure and applied mathematics. The standard example of such a problem is the traveling salesman problem were we are given some n cities and ask for the shortest path that visits each city exactly once.
That's a nutshell start on computational time complexity in computer science.