Asymptotic Notations

When it comes to analyzing the complexity of any algorithm in terms of time and space, we can never provide an exact number to define the time required and the space required by the algorithm, instead we express it using some standard notations, also known as Asymptotic Notations.

When we analyze any algorithm, we generally get a formula to represent the amount of time required for execution or the time required by the computer to run the lines of code of the algorithm, number of memory accesses, number of comparisons, temporary variables occupying memory space etc. This formula often contains unimportant details that don't really tell us anything about the running time.
 

Types of Asymptotic Notations

We use three types of asymptotic notations to represent the growth of any algorithm, as input increases:

1. Theta (Θ)
2. Big Oh(O)
3. Omega (Ω) 

Theta Notation, θ

The notation θ(n) is the formal way to express both the lower bound and the upper bound of an algorithm's running time.

Big Oh Notation, Ο

The notation Ο(n) is the formal way to express the upper bound of an algorithm's running time. It measures the worst case time complexity or the longest amount of time an algorithm can possibly take to complete.

Omega Notation, Ω

The notation Ω(n) is the formal way to express the lower bound of an algorithm's running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete.

Common Asymptotic Notations

Following is a list of some common asymptotic notations −

constant	−	Ο(1)
logarithmic	−	Ο(log n)
linear	−	Ο(n)
n log n	−	Ο(n log n)
quadratic	−	Ο(n2)
cubic	−	Ο(n3)
polynomial	−	nΟ(1)
exponential	−	2Ο(n)

Data structure

A data structure is a specialized format for organizing and the programmatic way of storing data so that data can be used efficiently. General data structure types include the array,stack, queue, linked list, graph, tree,file, record, table, the tree, and so on. Any data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropriate ways. In computer programming, a data structure may be selected or designed to store data for the purpose of working on it with various algorithms.

Data Structure = Related Data+ Permitted Operations.

Operations Performed On Data:
1) Storing
2) Deletion
3) Modifying
4) Insertion
5) Deletion
6) Searching
7) Sorting



                             

Prepositional Logic

Importance of Mathematical Logic
The rules of logic give precise meaning to mathematical statements. These rules are used to distinguish between valid and invalid mathematical arguments.
Apart from its importance in understanding mathematical reasoning, logic has numerous applications in Computer Science, varying from design of digital circuits, to the construction of computer programs and verification of correctness of programs.
 

Prepositional Logic

A proposition is the basic building block of logic. It is defined as a declarative sentence that is either True or False, but not both.
The Truth Value of a proposition is True(denoted as T) if it is a true statement, and False(denoted as F) if it is a false statement.

1. The sun rises in the East and sets in the West.
2. 1 + 1 = 2
3. 'b' is a vowel.

All of the above sentences are propositions, where the first two are Valid(True) and the third one is Invalid(False).
Some sentences that do not have a truth value or may have more than one truth value are not propositions.
For Example,

1. What time is it?
2. Go out and play.
3. x + 1 = 2.

The above sentences are not propositions as the first two do not have a truth value, and the third one may be true or false.
To represent propositions, propositional variables are used. By Convention, these variables are represented by small alphabets such as p,q,r,s .
The area of logic which deals with propositions is called propositional calculus or propositional logic.
It also includes producing new propositions using existing ones. Propositions constructed using one or more propositions are called compound propositions. The propositions are combined together using Logical Connectives or Logical Operators.

Truth Table
Since we need to know the truth value of a proposition in all possible scenarios, we consider all the possible combinations of the propositions which are joined together by Logical Connectives to form the given compound proposition. This compilation of all possible scenarios in a tabular format is called a truth table.

 OR (∨ ) − The OR operation of two propositions A and B (A ∨ B) is true if at least any of the propositional variable A or B is true.
The truth table is as follows −

A	B	A ∨ B
True	True	True
True	False	True
False	True	True
False	False	False

AND (∧  ) − The AND operation of two propositions A and B (A ∧ B
) is true if both the propositional variable A and B is true.
The truth table is as follows −

A	B	A ∧ B
True	True	True
True	False	False
False	True	False
False	False	False

 Negation (~) − The negation of a proposition A (¬ A is false when A is true and is true when A is false.
The truth table is as follows −

A	¬ A
True	False
False	True

 Implication / if-then ( → )  − An implication(A → B)() 
is the proposition “if A, then B”. It is false if A is true and B is false. The rest cases are true.
The truth table is as follows −

A	B	A → B
True	True	True
True	False	False
False	True	True
False	False	True

 If and only if(⇔) (A ⇔ B)
is bi-conditional logical connective which is true when p and q are same, i.e. both are false or both are true.
The truth table is as follows −

A	B	A ⇔ B
True	True	True
True	False	False
False	True	False
False	False	True

Tautology
A Tautology is a formula which is always true for every value of its propositional variables.
Example

The truth table is as follows −

A	B	A → B	(A → B) ∧ A	A ⇔ B
True	True	True	True	True
True	False	False	False	True
False	True	True	False	True
False	False	True	False	True

is "True", it is a tautology.

Contradiction
A Contradiction is a formula which is always false for every value of its propositional variables.
Example −

The truth table is as follows −

A	B	A ∨ B	¬ A	¬ B	(¬ A) ∧ ( ¬ B)	(A ∨ B) ∧ [( ¬ A) ∧ (¬ B)]
True	True	True	False	False	False	False
True	False	True	False	True	False	False
False	True	True	True	False	False	False
False	False	False	True	True	True	False

is “False”, it is a contradiction.


Contingency

A Contingency is a formula which has both some true and some false values for every value of its propositional variables.  
Example −

The truth table is as follows −

A	B	A ∨ B	¬ A	(A ∨ B) ∧ (¬ A)
True	True	True	False	False
True	False	True	False	False
False	True	True	True	True
False	False	False	True	False

has both “True” and “False”, it is a contingency.