INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS.

Introduction to data structures and algorithms.

What is a data structure?
A data structure is a specialized format for organizing, processing, retrieving and storing data. Anything that can store data is called a data structure. Primitive data structures
include an integer, Float, Boolean, Char etc while complex data structures include linked lists,trees,graphs,stacks,queues etc.

What is an algorithm?
Algorithms are all about problem solving. An algorithm is a procedure used for solving a problem or performing a computation. Every algorithm must satisfy the following:

1.Input- There must be an external input to the algorithm.
2.Output- There algorithm must eventually give out at least one output.
3.Definiteness- Every step of the algorithm should be clear and well defined.
4.Finiteness- The algorithm should have finite number of steps.
5.Correctness- Every step of the algorithm must generate a correct output.
An algorithm must be efficient and use less memory. This performance is arrived at using time and space complexity.
TIME COMPLEXITY
Time complexity is the amount of time taken by an algorithm to run, as a function of the length of the input.
The different types of time complexities include:

1. Constant time – O (1) -Irrespective of the input size n, the runtime will always be the same.

2. Linear time – O (n) -This is when the running time increases linearly with the length of the input.

3. Logarithmic time – O (log n) -This is when it reduces the size of the input data in each step eg binary search tree.

4. Quadratic time – O (n^2) - This is where the running time increases non-linearly (n^2) with the length of the input.

5. Cubic time – O (n^3)
   SPACE COMPLEXITY
   The space complexity of an algorithm quantifies the amount of space taken by an algorithm to run as a function of the length of the input.
   Space complexity differs from auxiliary space in that whereas space complexity quantifies the total space used by the algorithm, auxiliary space quantifies the extra space that is used in the algorithm apart from the given input.