Fundamentals of Algorithms and Data Structures

Introduction to Algorithms

An algorithm is a sequence of steps designed to solve a specific problem. In other words, an algorithm is a method for solving this problem. In this sense, the term “algorithm” is used to describe a method for solving any problem, including everyday ones. However, in this case, we will be discussing algorithms for computer calculations.

The term “algorithm” itself comes from the name of the Persian mathematician Al-Khwarizmi, whose works played an important role in the development of mathematics as a science.

An algorithm may have input data on which calculations are performed, and it may also have an output—a single value or a set of values. Essentially, the algorithm’s task is to transform input values ​​into output values.

An important criterion for an algorithm is its efficiency. An algorithm can perfectly solve a given problem, but still be inefficient. Typically, algorithm efficiency refers to the time it takes to execute.

The total execution time of the program depends on two factors:

• execution time of each operator
• frequency of execution of each operator

The execution time of each statement depends on the execution environment, operating system, and other system characteristics.

Depending on their efficiency, there are many types of algorithms, among which the following types of algorithms can be distinguished (listed in order of decreasing efficiency):

• Constant (1)An application performs a fixed number of operations that typically require constant time.

  An example would be the following set of operations:

  1 2 3 4 5 6 7 8 9

  int x = 10; if(x > 0) { x--; } else { x++; }

• Logarithmic (logN)It runs slower than constant-time programs. An example of such an algorithm is the binary search algorithm.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  public static int Rank(int key, int[] numbers) { int low = 0; int high = numbers.Length - 1; while (low <= high) { // find the middle int mid = low + (high - low) / 2; // if the search key is less than the value in the middle // then the upper bound will be the element before the middle if (key < numbers[mid]) high = mid - 1; else if (key > numbers[mid]) low = mid + 1; else return mid; } return -1; }

  For example, if we have numbers8 elements in an array, then to find the element we need, we need to sequentially divide the number of elements by 2. That is, to find the desired element, we need to execute the while loop 3 times. And this result is precisely described by the logarithmic function: log ₂ 8 = 3;

  The growth of execution time with the growth of N will increase by some constant value.

• Linear (N)Typically found where the method is based on a loop. For example, the factorial function:

  1 2 3 4 5 6 7 8 9

  private static int Factorial(int n) { int result = 1; for(int i=1; i<=n; i++) { result *= i; } return result; }

  Here, the method’s execution depends on n. The number of times the loop will be executed depends on the value of n passed to the method. This means that the increase in the algorithm’s complexity for this method is proportional to the value of n, which is why it is called linear.

• Linear-logarithmic (NlogN)An example of such an algorithm is merge sort.
• Quadratic (N ² )Typically, methods that correspond to this algorithm contain two loops – an outer loop and a nested loop – that are executed for all values ​​up to N. An example would be a bubble sort program for an N-element array, in which, in the worst case, we need to iterate through N*N elements using two loops:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  private static void BubbleSort(int[] nums) { int temp; for (int i = 0; i < nums.Length - 1; i++) { for (int j = i + 1; j < nums.Length; j++) { if (nums[i] > nums[j]) { temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } } }

• Cubic (N ³ )Programs that follow this algorithm use three loops, for example:

  1 2 3 4 5 6 7 8 9 10 11

  char[] chars = new char[] { 'A', 'B', 'C' }; for(int i=0; i<chars.Length; i++) { for(int j=0; j<chars.Length;j++) { for(int k=0; k<chars.Length;k++) { Console.WriteLine($"{chars[i]}{chars[j]}{chars[k]}"); } } }

Here we’ve only discussed a few of the many types of algorithmic complexity that exist. They can be represented graphically as follows:

At the same time, several caveats should be made. This example presents an idealized model of algorithm complexity. But first, it’s important to note that this assumes the impact of the environment (the operating system) on program execution is negligible. However, in reality, the environment can naturally contribute to the final performance of an application.

Furthermore, in most cases, the complexity of an algorithm depends on the presence of loops. A method without a loop with simple expressions has O(1) complexity, while a method with a single loop has O(N) complexity, which is theoretically worse than O(1). However, in reality, the presence of simple operators, even without a loop, can reduce performance. Much here again depends on the specific logic of the program.

Another aspect that can impact program execution is caching. Using caching allows for faster re-execution of an operation. Therefore, the execution time of the same operation may vary.

Explore More IT Terms