Book Image

C# Data Structures and Algorithms - Second Edition

By : Marcin Jamro
Book Image

C# Data Structures and Algorithms - Second Edition

By: Marcin Jamro

Overview of this book

Building your own applications is exciting but challenging, especially when tackling complex problems tied to advanced data structures and algorithms. This endeavor demands profound knowledge of the programming language as well as data structures and algorithms – precisely what this book offers to C# developers. Starting with an introduction to algorithms, this book gradually immerses you in the world of arrays, lists, stacks, queues, dictionaries, and sets. Real-world examples, enriched with code snippets and illustrations, provide a practical understanding of these concepts. You’ll also learn how to sort arrays using various algorithms, setting a solid foundation for your programming expertise. As you progress through the book, you’ll venture into more complex data structures – trees and graphs – and discover algorithms for tasks such as determining the shortest path in a graph before advancing to see various algorithms in action, such as solving Sudoku. By the end of the book, you’ll have learned how to use the C# language to build algorithmic components that are not only easy to understand and debug but also seamlessly applicable in various applications, spanning web and mobile platforms.
Table of Contents (13 chapters)

Computational complexity

In this final section, let’s take a look at the computational complexity of algorithms, focusing on both time complexity and space complexity. Why is this so important? Because it can decide whether your algorithm can be used in real-world scenarios. As an example, which of the following do you prefer?

  • (A) Absolutely the best route directions to work, but you receive them after an hour, when you are already at work.
  • (B) Good enough route directions to work, but you receive them within a few seconds, a moment after you enter your car.

I am sure that you chose Bme too!

Time complexity

First, let’s focus on time complexity, which indicates the amount of time necessary to run an algorithm as a function of the input length, namely n. You can specify it using asymptotic analysis. This includes Big-O notation, which is used to indicate how much time the algorithm will take with the increasing size of the input.

For example, if you search for the minimum value in an unsorted array of size n, you need to visit all elements so that the maximum number of operations is equal to n, which is written as O(n). If the algorithm iterates through each item in a two-dimensional array of size n x n, the time complexity is O(n*n), so it is O(n2).

There are various time complexities, including the ones presented here:

Figure 2.5 – Illustration of time complexities

Figure 2.5 – Illustration of time complexities

The first is O(1) and is named the constant time. It indicates an algorithm whose execution time does not depend on the input size. The exemplary operations consistent with the O(1) constraint are getting an i-th element from an array, checking whether a hash set contains a given value, or checking whether a number is even or odd.

The next time complexity shown here is O(log n), which is named the logarithmic time. In this case, the execution time is not constant, but it increases slower than in the linear approach. A well-known example of the O(log n) constraint is the problem of finding an item in a sorted array with binary search.

The third case is O(n) and is named the linear time. Here, the execution time increases linearly with the input length. You can take an algorithm for finding the minimum or maximum value in an unordered list or simply finding a given value in an unordered list as examples of the O(n) constraint.

The last time complexity shown here is the polynomial time, which is O(nm), so it can be O(n2) (quadratic time), O(n3) (cubic time), and so on. In this case, the execution time increases much faster than in the case of the linear constraint. It can involve solutions that use nested loops. Examples include the bubble sort, insertion sort, and selection sort algorithms. We'll cover these in Chapter 3, Arrays and Sorting.

Of course, there are even more time complexities available, among which you will find double logarithmic time, polylogarithmic time, fractional power time, linearithmic time, exponential time, and factorial time.

Space complexity

Similar to time complexity, you can specify the space complexity using asymptotic analysis and the Big-O notation. Space complexity indicates how much memory is necessary to run the algorithm with the increasing length of input. You can use similar indicators, such as O(1), O(n), or O(n2).

Where can you find more information?

In this chapter, only a very brief introduction to the subject of algorithms was presented. I strongly encourage you to try to broaden your knowledge regarding algorithms on your own. It is an extremely interesting and challenging topic. For example, you can learn more about various types of algorithms at and at, while about the computational complexity at I am keeping my fingers crossed for you success with algorithms!