Linear Data Structures

Linear Data Structures:

• 
  Arrays
  
• 
  Linked Lists
  
• 
  Stacks
  
• 
  Queues
  
• 
  Hash Tables
  

Non-Linear Data Structures:

• 
  Trees
  
• 
  Graphs
  

Big O notation
We use Big O to describe the performance of an algorithm. We use the big O notation to understand how much the cost of an algorithm increases. All we need is an approximation, not an exact value.
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

This method takes an array of integers and prints the first item on the console. It doesn’t matter how big the array is. We can have an array with one or 1 million items. All we are doing here is printing the first item. So, this method has a single operation and takes a constant amount of time to run. You don’t care about the exact execution time in milliseconds because that can be different from one machine to another or even on the same machine. All we care about is that this method runs constant time and we represent it using the O(1). This is the runtime complexity of this method. So in this example, the size of our input doesn’t matter. This method will always run in constant time or O(1).
What if we duplicate this line? We have two operations. Both these operations run in constant time. So the runtime complexity of this method is big O(2).

When talking about the runtime complexity, we don’t really care about the number of operations. We just want to know how much of an algorithm slows down as the input grows larger. So, in this example, whether we have one or 1 million items, our method runs in constant time. So, we can simplify this by writing down O(1), meaning constant time.


O(n) – simple loops running linear time or O(n).
Here we have a slightly more complex example. You have a loop, so we’re iterating over all the items in this array and printing each item on the console. This is where the size of the input matters. If you have a single item in this array, you’re going to have one print operation. If you have a million items, obviously we’re going to have a million print operations. So, the cost of this algorithm grows linearly and in direct correlation to the size of the input. So, runtime complexity of this method is O(n) and n represents size of the input. So, as n grows, the cost of this algorithm also grows linearly.