Hi!
Today's lesson will be slightly different from the rest. It will differ in that it is only indirectly related to Java.
That said, this topic is very important for every programmer. We're going to talk about algorithms.
What is an algorithm? In simple terms, it is some sequence of actions that must be completed to achieve a desired result.
We use algorithms often in everyday life.
For example, every morning you have a specific task: go to school or work, and at the same time be:

- Clothed
- Clean
- Fed

- Wake up using an alarm clock.
- Take a shower and wash yourself.
- Make breakfast and some coffee or tea.
- Eat.
- If you didn't iron your clothes the previous evening, then iron them.
- Get dressed.
- Leave the house.

- Buy or download the 1961 edition of Webster's Third New International Dictionary.
- Find every name from our list in this dictionary.
- On a piece of paper, write the page of the dictionary on which the name is located.
- Use the pieces of paper to sort the names.

`for`

loop that performs this task
```
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
```

What is the complexity of this algorithm? Linear, i.e. O(n).
The number of actions that the program must perform depends on how many numbers are passed to it.
If there are 100 numbers in the array, there will be 100 actions (statements to display strings on the screen). If there are 10,000 numbers in the array, then 10,000 actions must be performed.
Can our algorithm be improved in any way? No.
No matter what, we will have to make N passes through the array and execute N statements to display strings on the console.
Consider another example.
```
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(0, 20202);
numbers.add(0, 123);
numbers.add(0, 8283);
}
```

We have an empty `LinkedList`

into which we insert several numbers. We need to evaluate the algorithmic complexity of inserting a single number into the `LinkedList`

in our example, and how it depends on the number of elements in the list.
The answer is O(1), i.e. constant complexity. Why?
Note that we insert each number at the beginning of the list. In addition, you will recall that when you insert a number into a `LinkedList`

, the elements don't move anywhere. The links (or references) are updated (if you forgot how LinkedList works, look at one of our old lessons).
If the first number in our list is `x`

, and we insert the number y at the front of the list, then all we need to do is this:
```
x.previous = y;
y.previous = null;
y.next = x;
```

When we update the links, we don't care how many numbers are already in the `LinkedList`

, whether one or one billion.
The complexity of the algorithm is constant, i.e. O(1).
GO TO FULL VERSION