Linear time Algorithms O(n)

Algorithms are an integral part of computer science, and in fact our day to day lives. We use algorithms all the time without thinking about it, in a way our brains are wired to figure out solutions to problems. As computer programmers and application developers we need to know how to translate these solutions into code and ideally effective and efficient code.

In this tutorial series I am going to break a bit from my normal C# Google tutorials. Over the last several months I have seen a lot of people talk about algorithm performance and big O. This is something I learned a very long time ago in collage. After more then 20 years a lot of this has become instinct to me rather then something I was doing with direct intent. When designing an algorithm it is best to know exactly what you are doing and why you are doing it. As someone who has been an application developer for more then twenty years somethings become more instinctive and less purposeful. I have always enjoyed writing tutorials so I thought that I would write a tutorial series on this, in order to get it strait in my own head. I intend to put my normal spin on the series. This will be as simple as possible and the examples will just work.
[wp_ad_camp_3]

Algorithm series

What is linear time?

Linear time is a concept where by time is seen sequentially, as a series of events that are leading toward something: beginning, and an end.

I like to think of linear as step by step. Start at the beginning and slowly work your way to the end. With programming a for loop is a great example of linear time.
for i := 1 to 100 do print i; do
Each time we step though the loop is incremented by one. Having your algorithm work in linear time can be quite efficient.

Linear Search

Lets say that we have an array of integers.

var data = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

How would you go about finding the number 6. There are a few ways of doing it.

public static int? FindPositionOfNumberWitinArray(int[] data, int find)
{
     for (int i = 0; i <; data.Length; i++)
     {
         if (data[i] == find)
             return i;
     }
     return null;
}

The method above loops though each item in the array testing it until it finds the correct item. Lets think of some edge ceases. Best case the item we are looking for will be the first item worse case it will be the last. How many items there are in the array is going to tell you how long the method will run. Every time we increase the amount of data we have we are going to be potentially increasing the run time.

Time Complexity

Linear search runs at worst case in linear time. That means that if you have n items in your array and the item you are looking for is the last one you are going to have to make n comparisons.
[wp_ad_camp_5]

Improvements

Can you think of any way to improve the above search? I can think of one if we knew the size of our array and the data was sorted. Then we could test to see if the number was towards to the end of the array we could start our loop backwards.

public static int? FindPositionOfNumberWitinArray(int[] data, int find)
{
     for (int i = data.Length - 1; i > 0; ; i--)
     {
         if (data[i] == find)
             return i;
     }
     return null;
}

Our new worse case would be if the item was exactly in the middle. Which is better than before, but this is still a linear search. However if our data was something like this

var data = new int[] { 1, 10, 11, 12, 13, 14 };

If we want to find number 11 we might think that starting at the end would be better but it wont. This is why you really need to know your data.

Conclusion

Before you even begin to code a new algorithm you must first consider things about the data it self. Determine out what your best and worse case will be, look at the amount of data you have, and the specs of the machine that will be running the algorithm.

An algorithm is said to take linear time, or O(n) time, when its worst case complexity is O(n). This means that the more data you have the more time it will take to process it, the increase is linear or in a line. Each item in the algorithm will have to be processed one at a time. Linear time is the best possible time complexity in situations where the algorithm has to sequentially read its entire input. Another example would be adding up each value in an array.

Join me in the next tutorial Algorithms Quadratic time O(n²).

Google API Obsessed Content Creator