100 Days 100 Algorithms: Day-0

Hi everyone!

Starting to a beautiful day, I intend to start to something new and progressive.
Here, I will try to implement and upload 100 different algorithms in 100 consecutive days.

Firstly, who am I?
I am an algorithms enthusiast that also loves coding. I am interested in every modern subject of science. From Physics to Bioengineering, from Organic Chemistry to Topology...

Why do I do this work over here?
Because it is a new and alive environment that can fuel me to move forward better. I love sharing and teaching and am a supporter of open source projects. Thus, I thought it would be a good opportunity for all of us here to share and learn together.

What do you need to know to understand what I am talking about?
Having basic knowledge of mathematics, run-time complexity and a little bit of C++ is recommended. However, I shall walk you through everything I explain. So do not worry if you are not familiar with what I am talking about.

To begin with, what is an algorithm really?
An algorithm consists of a set of rules in an order to apply a specific task on a specific input. An algorithm's purpose may be solving a problem, generating random numbers etc.
For example, finding nth Fibonacci number using a computer requires an algorithm. A solving mechanism...

What is runtime complexity?
Runtime complexity of an algorithm is basically how long that algorithm will take to generate the output we expect.
However, as you know, every computer has a different power of computation and so they take different time to finish the same algorithm. Therefore, thinking about runtime complexity as a mathematical concept will help better.

Let's move on with an example.
Assume that you are a computer and your user gives you a set of numbers and expects you to return the smallest one to him back.
While getting the set, as you do not have human eyes, you do not know the numbers themselves. Thus, you will have to go through every element of the set right?

e.g. int array[n] = {23,1,232,67,435,3,4324,423 ...};

The line above shows an array implementation from C++. It basically says that we have a set of numbers in order and there are n of them.

Going back to being a computer, we will start from the first element and look for the smallest element right? Yes.
So, you need to look at basically n numbers. Let's ignore the operation where you compare the current element you are looking at with the smallest element you have seen so far.

In Computer Science we say that your algorithm runs in O(n) time.
Why?
Because the duration will only depend on your input size.

To grasp it better, let's consider another example.
Let's say you are a computer and the input is a matrix of sizes n and m. That is, it has n rows and m columns.

e.g. int array[n][m] = {{3,7,213,31..},{34,98,432,12...},...};

The line above shows a matrix implementation in C++. Let's assume you are also looking for the smallest element in the array. What is your run time if you are going to look at every element once?

Well, that is obvious.
O(nm) because you have a total of nm elements.

So, that is what runtime complexity basically means.

Tomorrow, I will start with my first algorithm which is Binary Search.

Till then, why don't you think about the complexity of finding out if an input number is prime or not. Assume that to check if it's a prime number or not, you are trying to divide it by every integer smaller than the input.

Peace!