# Analysis of Algorithms

> It is convenient to have a measure of the amount of work involved in a computing process, even though it be a verycrudeone. We may count up the number of times that various elementary operations are applied in the whole process and then given them various weights. We might, for instance, count the number of additions, subtractions, multiplications, divisions, recording of numbers, and extractions of figures from tables. In the case of computing with matrices most of the work consists of multiplications and writting down numbers, andwe shall therefore only attempt to count the number of multiplications and recordings.
>
> — Alan Turing

Consider these questions to be solved:

* Given N distinct integers, how many zeros is there?
* Given N distinct integers, how many combination of two sum to exactly zero?
* Given N distinct integers, how many triples sum to exactly zero?

Lets look at Java code that would be a first quick and dirty answer for given problem.

## Given N distinct integers, how many zeros is there?

`O(n)`

```
class Zeros {

    public int findZeros(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i == 0) {
                count++;
            }
        }
        return count;
    }
}
```

## Given N distinct integers, how many combination of two sum to exactly zero?

`O(n^2)`

```
class Doubles {

    public int findZeroSums(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] + arr[j] == 0) {
                    count++;
                }
            }
        }
        return count;
    }
}
```

## Given N distinct integers, how many triples sum to exactly zero?

`O(n^3)`

```
class Triplets {

    public int findZeroSums(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                for (int k = j + 1; k < arr.length; k++) {
                    if (arr[i] + arr[j] + arr[k] == 0) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```

Here is table that contains all basic classifications of Big-O complexity.

![](/files/-M3wYZFe2B40hxQmpTg1)

Here is a short overview of Big-O complexity classifications.![](/files/-M3wYZFnCV4s0Q9kpHn5)

## Memory

Another aspect we need to consider when developing an algorithm is memory consumption. Typical memory consumption is shown in the tables below. In Java, there is 16 bytes overhead for each object and 8 bytes for an object reference. Array has 24 bytes overhead. ![](/files/-M3wYZFpqa3SRt-ZdteJ)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ondrej-kvasnovsky-2.gitbook.io/algorithms/analysis-of-algorithms.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.