What is
an Algorithm
An
algorithm is a finite set of instructions or logic, written in order, to
accomplish a certain predefined task. Algorithm is not the complete code or
program, it is just the core logic (solution) of a problem, which can be
expressed either as an informal high level description as pseudocode or
using a flowchart.
Every
Algorithm must satisfy the following properties:
- Input- There should be 0 or more inputs supplied externally to the algorithm.
- Output- There should be at least 1 output obtained.
- Definiteness- Every step of the algorithm should be clear and well defined.
- Finiteness- The algorithm should have finite number of steps.
- Correctness- Every step of the algorithm must generate a correct output.
An algorithm is said to be
efficient and fast, if it takes less time to execute and consumes less memory
space. The performance of an algorithm is measured on the basis of following properties:
- Time Complexity
- Space Complexity
Space Complexity
It’s the
amount of memory space required by the algorithm, during the course of its
execution. Space complexity must be taken seriously for multi-user systems and
in situations where limited memory is available.
An
algorithm generally requires space for following components:
- Instruction Space: It’s the space required to store the executable version of the program. This space is fixed, but varies depending upon the number of lines of code in the program.
- Data Space: It’s the space required to store all the constants and variables (including temporary variables) value.
- Environment Space: It’s the space required to store the environment information needed to resume the suspended function.
To learn about Space
Complexity in detail, jump to the Space Complexity tutorial.
Time
Complexity
Time
Complexity is a way to represent the amount of time required by the program to
run till its completion. It's generally a good practice to try to keep the time
required minimum, so that our algorithm completes its execution in the minimum
time possible. We will study about Time Complexity in details in later sections.
What is
Time Complexity
Time complexity
of an algorithm signifies the total time required by the program to run till
its completion.
The time
complexity of algorithms is most commonly expressed using the big O
notation. It's an asymptotic notation to represent the time complexity. We will
study about it in detail in the next tutorial.
Time
Complexity is most commonly estimated by counting the number of elementary
steps performed by any algorithm to finish execution. Like in the example
above, for the first code the loop will run n number of times, so the time complexity will be n at least and as the value of n will increase the time taken will also increase. While for
the second code, time complexity is constant, because it will never be
dependent on the value of n, it will always give the result in 1 step.
And since
the algorithm's performance may vary with different types of input data, hence
for an algorithm we usually use the worst-case Time complexity of
an algorithm because that is the maximum time taken for any input size.
In modern world, Data and
its information is a very essential part and various implementations are being
made to store in different ways. Data are just collection of facts and figures
or you can say data are values or set of values that is in particular format. A
data item refers to a single set of values. Data items are then further
categorized into sub items which are the group of items which are not are
called plain elementary form of items. Let us take an example where the name of
the student may be divided into three sub items namely: first name, middle name
and last name. But the ID that is assigned to a student would normally be
considered as a single item.
In the example mentioned
above such as ID, Age, Gender, First, Middle, Last, Street, Area etc are elementary
data items, whereas (Name, Address) are group data items.