Assignment of DSA

Submitted to:
Dr. Muhammad Awais

Submitted by:
4203 M. Khalid Irfani
4213 Atif Hameed
4225 Qaiser Nadeem
4235 Munazza Ashraf
4243 Rameela Mushtaq
4255 Sahaab Tariq

Semester:
3rd (Morning .A)

Session:
2020-2024

Faculty of Physical Science,

Government College University
Faisalabad.
Q: Describe types of Time complexity of Algorithms. Define the
Terms NP Hard and NP complete and give examples of such
Algorithms with the explanation why they are NP Hard and NP
complete .
Time Complexity Introduction
Time complexity can define the effectiveness of an algorithm. While there is more
than one way to solve the problem in programming, knowing how the algorithm
works efficiently can add value to the way we do programming. To find the
effectiveness of the program/algorithm it is necessary to know how to evaluate them
using Time complexity can make the program behave in required optimal conditions,
and by doing so, it makes us efficient programmers.

Time Complexity
Time complexity is the computational complexity that describes the amount of computer
time it takes to run an algorithm. Time complexity is commonly estimated by counting
the number of elementary operations performed by the algorithm, supposing that each
elementary operation takes a fixed amount of time to perform. Thus, the amount of time
taken and the number of elementary operations performed by the algorithm are taken to
be related by a constant factor.

The amount of time taken by an algorithm is a function of the length of input only.
Here, the length of input indicates the number of operations to be performed by the
algorithm.

The time complexity is commonly expressed using big O notation, typically O(n), O(n
log n), O(na), O(2a),etc…, where n is the size in units of bits needed to represent the
input.

Cases to analyze the Algorithm

 Worst-case complexity
 Average-case complexity
  Best-case complexity

Worst-case complexity:

The worst-case time-complexity indicates the longest running time performed by an

algorithm given any input of size n, and thus guarantees that the algorithm will finish
in the indicated period of time. The order of growth (e.g. linear, logarithmic) of the
worst-case complexity is commonly used to compare the efficiency of two
algorithms.

Average-case complexity:

The average-case complexity of an algorithm is the amount of some computational

resource (typically time) used by the algorithm, averaged over all possible inputs. It
is frequently contrasted with worst-case complexity which considers the
maximal complexity of the algorithm over all possible inputs.

Best-case complexity:

In best-case time complexity minimum time needed to execute an algorithm for

an input of size n.

Types of Time complexity

There are different types of time complexities used, let’s see one by one:

1. Constant time – O (1)

2. Linear time – O (n)

3. Logarithmic time – O (log n)

4. Quadratic time – O (n^2)

5. Cubic time – O (n^3)

6. Polynomial time

7. Exponential time_O(2^n)

8. Factorial time_O(n!)
Constant time – O (1):

An algorithm is said to have constant time with order O (1) when it is not dependent
on the input size n. Irrespective of the input size n, the runtime will always be the
same.

For Example :

int index = 5;
int item = list[index];
if (condition true) then
perform some operation that runs in constant time
else
perform some other operation that runs in constant time
for i = 1 to 100
for j = 1 to 200
Perform some operation that runs in constant time

Linear time – O (n)

An algorithm is said to have a linear time complexity when the running time
increases linearly with the length of the input. When the function involves checking
all the values in an input data, such function has Time complexity with this order
O(n).

For example:

A procedure that adds up all elements of a list requires time proportional to the length
of the list, if the adding time is constant, or, at least, bounded by a constant .

Logarithmic time – O (log n):

An algorithm is said to have a logarithmic time complexity when it reduces the size of
the input data in each step. This indicates that the number of operations is not the
same as the input size. The number of operations gets reduced as the input size
increases. Algorithms with Logarithmic time complexity are found in binary trees or
binary search functions.
For Example:

An example of logarithmic time is given by dictionary search. Consider a

dictionary D which contains n entries, sorted by alphabetical order. We suppose that,
for 1 ≤ k ≤ n, one may access the kth entry of the dictionary in a constant time.
Let D(k) denote this kth entry. Under these hypotheses, the test to see if a word w is in
the dictionary may be done in logarithmic time: consider

D (⌊ n/2⌋), where ⌊ ⌋ denotes the floor function. If w= D(⌊ n/2⌋) , then we are done. Else,
if w< D(⌊ n/2⌋), continue the search in the same way in the left half of the dictionary,
otherwise continue similarly with the right half of the dictionary. This algorithm is similar
to the method often used to find an entry in a paper dictionary.

Quadratic time – O (n^2):

An algorithm is said to have a non – linear time complexity where the running time
increases non-linearly (n^2) with the length of the input. Generally, nested loops
come under this time complexity order where for one loop takes O(n) and if the
function involves loop within a loop, then it goes for O(n)*O(n) = O(n^2) order.

. Polynomial time:

An algorithm is said to be of polynomial time if its running time is upper bounded by

a polynomial expression in the size of the input for the algorithm, that is, T(n) = O(nk) for
some positive constant k. Problems for which a deterministic polynomial time algorithm
exists belong to the complexity class P, which is central in the field of computational
complexity theory. Cobham's thesis states that polynomial time is a synonym for
"tractable", "feasible", "efficient", or "fast".
Examples:

 The selection sort sorting algorithm on n integers performs operations for some
constant A. Thus it runs in time and is a polynomial time algorithm.
 All the basic arithmetic operations (addition, subtraction, multiplication, division, and
comparison) can be done in polynomial time.
Maximum matchings in graphs can be found in polynomial time.

NP Hard and NP complete and give examples of such Algorithms with

explanation.
In computer science, there exist several famous unresolved problems, and P
(“Polynomial” time), NP (“Non-deterministic Polynomial” time), NP Hard and NP
complete is one of the most studied ones.
In the case of rating from easy to hard, we might label these as “easy”, “medium”,
“hard”, and finally “hardest”:

 Complexity Class P:
 P is the complexity class containing decision problems which can be solved
by a deterministic Turing machine using a polynomial amount of
computation time, or polynomial time.
 P is often taken to be the class of computational problems which are
"efficiently solvable" or "tractable“.
 Problems that are solvable in theory, but cannot be solved in practice
 P is known to contain many natural problems, including the decision
versions of linear programming, calculating the greatest common divisor,
and finding a maximum matching.

 Complexity Class NP
 NP ("Nondeterministic Polynomial time") is the set of decision problems
solvable in polynomial time on a nondeterministic Turing machine.
 It is the set of problems that can be "verified" by a deterministic Turing
machine in polynomial time.
 All the problems in this class have the property that their solutions can be
checked effectively.
 This class contains many problems that people would like to be able to
Solve effectively, including n the Boolean satisfiability problem (SAT)
  NP Complete
 The NP complete problems are the most difficult problems in NP
("nondeterministic polynomial time") in the sense that they are the ones
most likely not to be in P.
 If one could find a way to solve any NP complete problem quickly (in
polynomial time), then they could use that algorithm to solve all NP
problems quickly.
 At present, all known algorithms for NP complete problems require time
that is super polynomial in the input size.
 To solve an NP complete problem for any nontrivial problem size, generally
one of the following approaches is used:
 Approximation
 Probabilistic
 Special case

 NP-Hard :
 A Problem X is NP-Hard if there is an NP-Complete problem Y, such that Y
is reducible to X in polynomial time.
 NP-Hard problems are as hard as NP-Complete problems. NP-Hard
Problem need not be in NP class

Example of Np-hard problem:

 An example of an NP-hard problem is the decision subset sum problem:
That is a decision problem and happens to be NP-complete.

Algorithm:
STEP 1: initialize a list L to contain one element 0.
STEP 2: for each i from 1 to n do
STEP 3: let Ui be a list containing all elements y in L, and all sums xi + y for all
y in L.
STEP 4: sort Ui in ascending order
STEP 5: make L empty
STEP 6: let y be the smallest element of Ui , add y to L for each element z of Ui
in increasing order do, if y + ε T/n < z ≤ T then, y = z
STEP 7: add z to L
STEP 8: return the largest element in L.
Difference between NP-Hard and NP-Complete

NP-hard NP-Complete
 NP-Hard problems (say X) can be  NP-Complete problems can be
solved if and only if there is a solved by a non-deterministic
NP Complete problem(say Y) Algorithm/Turing Machine in
that can be reducible into X in polynomial time
polynomial time
 To solve this problem, it do not  To solve this problem, it must be
have to be in NP. both NP and NP-hard problems.
 Do not have to be a Decision  It is exclusively a Decision
problem. problem.
 Example: Halting problem,  Example: Determine whether a
Vertex cover problem, etc. graph has a Hamiltonian cycle,
Determine whether a Boolean
formula is satisfiable or not,
Circuit-satisfiability problem, etc