This book is written with theÂ objective of making you understand what an algorithm is and the importance of it in computer science. Since an algorithm becomes more powerful when used with proper data structures, we'll also walk you through various commonly used data structures in programming.

In this chapter, we're going to focus on theoretical definitions of algorithms and data structures. As we move forward, we'll learn about this in detail.

As this book's title says, we're going to use the Kotlin programming language in all of the examples provided here. You may be asking why Kotlin? Why not any other programming language? The answer would be that it's just a language preference. But as far as algorithms are concerned, they can be understood and practiced with any programming language.

This chapter will help us to understand the following topics:

- Algorithms and their importance
- The efficiency of an algorithm
- Data structures
- Complexity and notations, including Big O notationÂ

To practice the algorithms and data structures we'll learn from this book, we need the Kotlin compiler to be installed on our PC. There are many ways to set your PC up for this. Let's look into that. Here is the GitHub link of this book:

The GitHub URL for the chapter is here:

The Kotlin binary is released over GitHub. So you need to find the latest release and download the ZIPÂ fileÂ if you want to install the Kotlin compiler manually.Â Currently, the latest release is 1.2.40, which can be found atÂ this GitHub URL:Â https://github.com/JetBrains/kotlin/releases/tag/v1.2.40.Â After the Kotlin compiler has downloaded, unzip the downloaded ZIP file into a directory and add the `bin`

Â directory to your system path. This is the directory that contains all of the scripts to compile and run your code.

If you want to install the compiler via SDKMAN, Homebrew, or similar tools, then you can follow the official instruction mentionedÂ here:

https://kotlinlang.org/docs/tutorials/command-line.html.

To write Kotlin code, you can use any of your favorite editors and start writing. Once the code is written, you can save the file as `<filename>.kt`

and it's ready for compilation. Please note that Kotlin files are represented with theÂ `.kt`

extension.

For compiling the Kotlin code, you need to use the following command:

**kotlinc <filename>.kt -include-runtime -d <filename>.jar**

To run it, use the following command:

**java -jar <filename>.jar**

If you're comfortable with IDEs and want to use an IDE instead of a simple text editor, then you can choose IntelliJ IDEA as it works seamlessly with Kotlin. The steps for using Kotlin with IntelliJ IDEA are explained in the official documentation here:Â https://kotlinlang.org/docs/tutorials/getting-started.html.

If you're more familiar with Eclipse than IntelliJ IDEA, then follow the official documentation atÂ https://kotlinlang.org/docs/tutorials/getting-started-eclipse.htmlÂ and set it up.

In computer programming, the sole purpose of building any software is to solve a problem existing in the real world and make the world a better place to live in. When we talk about a solution to a problem, it's obvious that we're talking about the procedure to be followed to solve the problem.

Let's consider a case where your teacher comes to you and gives you a bunch of candy, asking you to distribute it equally among your classmates. If you consider this as a problem and try to achieve it with ease, then you might do it as follows:

- Count the number of candies you have.
- Count the number of students present in your class.
- Calculate how many candies should be given to each student.
- Ask all of the students form a queue so that no student can take the required candies twice.
- Start distributing the candies to each student.
- Maintain a separate group for students who already took candies.

As you can see, I've created six steps to solve the task. You might solve it in a different way. These steps are what we call algorithms in computer science.

So, in a nutshell, we can define algorithms as something that takes a value or a set of values as input, processes it, and returns a value or a set of values as output. In other words, we can say that algorithms are a solution to a well-defined computational problem.

In this book, we'll cover the most commonly used basic algorithms, for example, sorting algorithms, searching algorithms, hashing algorithms, and so on.

Let's look at some examples to understand algorithms. Consider the following code:

private fun add(x: Int, y: Int) = x + y

In the preceding code snippet, the code accepts two arguments as input and returns their sum as output. It satisfies the definition of the algorithm by taking some input, processing the input, and returning the result. Now, consider the following code:

val hourInMillis = 24 * 60 * 60 * 1000

In the preceding example, we can still argue that this is an algorithm. Here, the compiler takes `24`

, `60`

, `60`

, and `1000`

as input and multiplies all of them to get the single output and finally assigns the output back to the property named `hoursInMillis`

. Even though this type of code has nothing to do with the runtime, we can define this as a **compile-time algorithm**.

So, in conclusion, we can say that programs that solve complex computation problems aren't the only programs that can be called **algorithms**. Instead, any program (whether simple or complex), if that consumes some input to calculate and gives some output can be called asÂ an algorithm. For example, sorting and searching aren't the only processes that can be called algorithms; even a simple assignment can also be treated as anÂ algorithm.

This is the beauty of computer science theory. There's no single definition available for algorithms. We just have a few rules to categorize something as an algorithm. As long as your program satisfies those, we can argue that it's an algorithm.

We solved the previous example by taking a few steps, such as asking all students to stand in a queue and, once a student got candy, we moved them to a separate group. We could have also done the same task without asking them to maintain a queue or separating them into a separate group once they got the candy. But we did that to make the task go smoother. Of course, we could have done the task without these two sub-tasks, but that would have created a lot of confusion and made it tedious to finish the task on time.

If we consider that example, we can treat candies and students as data. And to solve the problem given by the teacher, we first structured the data and solved it with ease. This is what we call data structures in computer science.

In this book, we'll cover the most commonly used data structures such asÂ an array, string, list, linked list, stack, queue, tree, graph, and so on. The order isn't the same though. If we talk about data structures in front of others, people generally think about the earlier mentioned data structures. But this doesn't mean that these are the only data structures available. We've a lot more data structures available and ones that are commonly used. In addition to these commonly used data structures, we can also define our own data structures based on our business needs. We might customize data structures in two ways:

- Extend existing data structures
- Customize data structures

If we've a problem, that can be achieved with the help of list but with a slight modification, then we'll try to extend the existing `List`

class present in Kotlin's collection framework instead of creating a completely new data structure. For example, the problem statement says to have a list of names, only in uppercase. Of course, there's no existing data structure that can do this out of the box. So you need to extend the `List`

and modify it a bit as per our need. So that all existing functionality of `List`

gets inherited and works the same as earlier, except with the modified one. Let's see the code:

class UpperCasedList : ArrayList<String>() { override fun add(element: String): Boolean { return super.add(element.toUpperCase()) } override fun add(index: Int, element: String) { super.add(index, element.toUpperCase()) } override fun addAll(elements: Collection<String>): Boolean { return super.addAll(elements.map { it -> it.toUpperCase() }) } override fun addAll(index: Int, elements: Collection<String>): Boolean { return super.addAll(index, elements.map { it -> it.toUpperCase() }) } override fun set(index: Int, element: String): String { return super.set(index, element.toUpperCase()) } }

If you observe theÂ `UpperCasedList`

Â class, you will find that, instead of implementing every functionality of a list, we just tried to modify the functionality related to item-addition functions since our goal is to make sure the list will always contain names in upper case. So, we just extended the existing `ArrayList`

data structure and tried to override the required methods to modify it as per our needs.

We can use our custom data structure like this:

fun main(args: Array<String>) { val names = UpperCasedList() names.add("Chandra") names.add("Rivu") println("Names in upper case : $names") // Output - [CHANDRA, RIVU] }

There might be many different types of problems you would like to solve, that can't be done using existing data structures or by modifying them. In this case, we need to define our own data structures from scratch. Consider the following code:

data class User(val firstName: String, val lastName: String, val phone: String, val email: String)

As shown in the preceding example, we need a structure that contains all attributes related to users using the software. These type of data structures can't be present in the existing set of data structures. Since these types of data structures are completely based on your business requirements, it's your responsibility to design them on your own. If you're considering those that can manage a collection of items (array, string, list, tree, graph, and more) and are only eligible to be called data structures, then you might want to rethink. In addition to these previously mentioned structures, custom objects we create for our problems (for example, user, customer, seller, and so on) can also be considered data structures.

So far, we've gained a good understanding of what an algorithm is and how data structures can be used in an algorithm to make it work better. In our day-to-day life, any task can be completed in many ways. Similarly, in computer science, any computational problem can be solved using many solutions; in other words, they can be solved using many algorithms. Since we've a one-to-many relationship with respect to the problem versus solutions, we might easily get confused while choosing a solution for a particular problem. This is the time for us to understand how to analyze an algorithm and choose the one that suits our problem.

Whenever we're trying to fix a particular computational problem, it's obvious that we'll consider all possible algorithms that can solve it. But we can't use them all together while writing our solution. In this case, we need to analyze all of the possible algorithms and choose the most appropriate one. Usually, we analyze an algorithm based on time complexity and space complexity.

The time complexity of an algorithm defines the time taken by it to produce the output for a given input. It quantifies the time taken by the algorithm; in other words, we can define time complexity as the performance of an algorithm. The better the time complexity, the better the performance of the algorithm.

We can simply argue that, instead of choosing a most performant algorithm for our problem, why can't we just increase the hardware capacity so that it can run the instructions much faster? Though the argument looks valid, it isn't. Even if we increase the hardware capacity, it's still a wise decision to choose the most performant algorithm for any problems we have.

The space complexity of an algorithm defines the space (memory) consumed by it to produce the output for a given input. In other words, we can say that the algorithm with better space complexity consumes or requires less memory to execute.

Even for space complexity, we can argue that, instead of choosing an algorithm that requires less memory, we can simply increase the memory of our computer to get rid of this issue. But it's always wise to choose an algorithm that consumes less memory.

We might face many issues while choosing an algorithm for any problem. One such issue is time complexity versus space complexity. We might find the following mentioned behavior of an algorithm:

- Faster in execution and consumes less memory
- Faster in execution but consumes more memory
- Slower in execution but consumes less memory
- Slower in execution and consumes more memory

Out of all of the preceding four behaviors, it's clear that algorithms with the first behavior should always be chosen over others, whereas the fourth behavior should always be avoided as much as possible. If we end up with algorithms of the second or third behavior being chosen for solving our problem, then we should choose one of them as per the need. Let's consider that you have a problem, that can be solved using two different algorithms; one algorithm is faster but consumes more memory whereas the other one consumes less memory but is slower in execution. In such a situation, you need to decide which algorithm best suits your requirements. You may need to ask yourself a question, and that isâ€”is solving and replying faster more important, or solving with less memory?

There are lots of tools available in our software world that can measure how much time is taken by an algorithm (a function) and how much memory it consumed. Usually, these tools are calledÂ **profilers**. If a profiler can measure the time and space complexity of anÂ algorithm we're writing, then why do we need to study them? The simple answer to this is profilers can measure time complexity in terms of milliseconds or nanoseconds and space complexity in terms of a number of bytes or bits consumed, whereas complexity analysis isn't meant to measure an algorithm the same way a profiler does. Instead, it's used to measure an algorithm at the idea level. For example, theÂ profiler can provide different output about an algorithm when run in two different machines, whereas the complexity analysis of that algorithm tells you the same thing irrespective of the machine you run or theÂ language you code in. By analyzing the complexity of any algorithm, we usually get answers to the following questions:

- How much time does it take to generate or calculate the output?
- How much memory does it need to solve the problem?
- How does it behave when the input size grows?
- Does it get faster or slower?Â If slower, how much slower? Does it get four times slower for two times the input size?
- What relationship does the time have with respect to the input size?

So far, we've understood why analyzing theÂ complexity of an algorithm is really important. Now it's time to understand how to analyze the complexity. Before moving ahead with the how-to part, let's understand that, once the complexity of anÂ algorithm is analyzed, there should be some way to represent it. For that, we usually use different notations.

As mentioned earlier, an algorithm can behave differently based on the size of the input given to it. And in the computer world, if you're building software, your algorithm should be prepared for any size of input. So, it's obvious that we need to analyze the complexity of every possible case.

TheÂ complexity of anÂ algorithm can broadly fall into the following three categories:

**Best case analysis**: Best case defines the minimum time required by an algorithm to produce the output. It's also represented as Omega notation (Î©).**Average case analysis**: Average case defines the average time required by an algorithm to produce the output for different sized input. It's also represented as Theta notation (Î¸).**Worst case analysis**: Worst case defines the maximum time required by an algorithm to produce the output. It's also represented as a Big O notation (O).

Before going ahead with examples and explaining the ways we can analyze an algorithm, let's understand how to count the number of instructions present in a particular piece of code.

Let's consider the following example, which identifies the odd and even numbers from 0 to 20 and prints them:

val x = 10 val y = x * 2 for (i in 0..y) { if (i % 2 == 0) { println(â€œ$i is Evenâ€) } else { println(â€œ$i is Oddâ€) } }

Let's break down the code to understand it better, as follows:

- The first line,
`val x = 10`

, requires one instruction, that is, assigning the value`10`

to`x`

. - The second line,
`val y = x * 2`

, requires three instructions. The first instruction is to look for`x`

, the second instruction is to multiply it by`2`

,Â and the third instruction is to assign the result to`y`

. - The third line,
`for (int i = 0; i < y; i++)`

,Â will run two more instructions in the first iteration of the loop. One is the assignment instruction,`i = 0`

,Â and the other one is the comparison instruction,

. After the first iteration, there are two more further iterations, that is,*i < y*`i++`

and`i < y`

. So the total for instructions here is*4n*. - From the fourth line onwardÂ (the body of theÂ
`for`

loop), for every iteration, the body will run a few more instructions, such asÂ`i % 2`

and result is 0Â and then, based on output, print instruction. Moreover, the print instruction is dependent on the result of a condition that itself depends on the condition of theÂ`for`

loop. So the total for instructions here is*2n (mod and comp) + 2n (concat and print) = 4n*. Note that the counting of instructions might not be accurate; we're doing it to understand the process. For example, string concat might not be a single instruction. Similarly, printing to console also might have multiple instructions. But we're considering those as one instruction to understand them better.

We can easily notice that the instructions count is getting tougher and tougher and we don't really need to deal with this tedious process. For example, instead of saying the complexity of the preceding algorithm is *f(n) = 1 + 3 + 4n + 4n = 4 + 8n*, we can simplify it further.

Since our main intention behind analyzing theÂ complexity of an algorithm is to identify how it behaves when the input grows or shrinks, we can ignore the instructions, which are always constant.

In the previous example, *f(n) = 4 + 8n*, it's clear that *4* and *8* never change, so by ignoring those, we can conclude *f(n) = n*. Here, we ignored all of the factors that don't change based on the input and considered only those factors that change based on the input. This is what we callÂ **asymptotic behavior**.

Let's see some examples:

*f(n) = 3n + 5*can be consideredÂ*f(n) = n**f(n) = 5*can be consideredÂ*f(n) = 1**f(n) = n*can be consideredÂ^{2}+ 3n + 5*f(n) = n*^{2}

In simple terms, we can summarize the asymptotic behavior of an algorithm as follows:

- Any program that doesn't have any loop has
*f(n) = 1.* - Any program with one
`for`

loop has*f(n) = n.* - Any program with one nested
`for`

loop (`for`

loop inside another`for`

loop) has*f(n) =Â n*^{2}.

With the preceding theory, let's try to analyze the worst, best, and average case of an algorithm. Let's consider an example of searching for an element from a given array. So the code will look as follows:

private fun find(input: IntArray, item: Int) { for (i in input.indices) { if (input[i] == item) { print("Item found at index - $i") } } }

Please note that the preceding code isn't written using proper Kotlin idiomatic syntax purposefully, to make you understand things better.

Let's say the input array is `[1,5,67,56,38,97,34,50,81]`

and we're trying to search for the following numbers:

`1`

: This can be found in the first iteration itself. This is an example of theÂ best case.`38`

: Since it's somewhere in the middle of the input, we can get the result in approximately*n/2*iterations (*n*is the length of the input array). This is an example of anÂ average case.`81`

: Since it;s the last item of the input array, the result will come at the*n*iteration.^{th}`102`

: Since it isn't present, the result will be produced at theÂ*n*iteration.^{th}

As we can see, based on the item we're searching for, the number of iterations are varied. So we should consider all cases during our analysis. Since it's always a best practice to be prepared for the worst, we prefer analyzing the worst case more often. Let's see the final analysis for the preceding search algorithm:

Best Case - Î©(1) Average case - Î¸(n/2) Worst case - O(n)

Since we don't consider the constant factors while performing complexity analysis, we can consider `Î¸(n/2)`

as `Î¸(n)`

. But please note that here,Â `O(n) > Î¸(n)`

.

So far, we've understood what an algorithm is and how it can be used with any data structures to solve problems easily. We also understood how to analyze the complexity of an algorithm. But this is just the beginning. As the chapters go on, all of the examples we discuss will relate to complexity analysis and similar information.

We will discuss about many commonly used data structures in further chapters and will try to do the complexity analysis for all those data structures and algorithms.