Big Omega is the reverse Big O, if Big O is used to describe the upper bound (worst - case) of a asymptotic function, Big Omega is used to describe the lower bound (best-case).

(i) BigO
(ii) BigW
(Iii) Big \(\mu \)

A way of designing algorithm is called algorithmic strategy

(i) Time factor
(ii) Space factor

Analysis of algorithms and performance evaluation can be divided into two different phases:
(i) A Priori estimates: This is a theoretical performance analysis of an algorithm. Efficiency of an algorithm is measured by assuming the external factors.
(ii) A Posterori testing: This is called performance measurement. In this analysis, actual statistics like running time and required for the algorithm executions are collected.

(i) Analysis of an algorithm usually deals with the running and execution time of various operations involved.
(ii) The running time of an operation is calculated as how many programming instructions is executed per operation

Efficiency of an algorithm is defined by the utilization of time and space complexity

Examples for data structures are arrays, structures, list, tuples, dictionary.

A searching algorithm is the step-by step procedure used to locate specific data among a collection of data. There are two types of searching are.
(i) Linear Search
(ii) Binary Search

Sorting is a method of arranging group of items in ascending or descending order. Various sorting techniques in algorithms are Bubble sort, Quick sort, Heap sort, Selection sort, Insertion sort.

The following shows a simple Dynamic programming approach for the generation of Fibonacci series.
Initialize f0 = 0,f1 =1
Step 1 - Print the initial values of Fibonacci f0 and f1
Step 2 - Calculate fibanocci fib \(\leftarrow \) f0+ f1
Step 3 - Assign f0\(\leftarrow \) fl , f1\(\leftarrow \) fib
Step 4 - Print the next consecutive value of fibanocci fib
step 5 - Goto step-2 and repeat until the specified number of terms generated
For example if we generate fibobnacci series upto 10 digits, the algorithm will generate the series as shown below:
The Fibonacci series is : 0 1 1 2 3 5 8 13 21 34 55

(i) Start from the first element i.e., index-0, we search the smallest element in the array, and replace it with the element in the first position.
(ii) Now we move on to the second element position, and look for smallest element present in the sub-array, from starting index to till the last index of sub - array.
(iii) Now replace the second smallest identified in step-2 at the second position in the or original array, or also called first position in the sub array.
(iv) This is repeated, until the array is completely sorted.

(i) Start with the first element i.e., index = 0, compare the current element with the next element of the array.
(ii) If the current element is greater than the next element of the array, swap them.
(iii) If the current element is less than the next or right side of the element, move to the next element. Go to Step 1 and repeat until end of the index is reached.

Start with the middle element:
(I) If the search element is equal to the middle element of the array i.e., the middle value = number of elements in array/2, then return the index of the middle element.
(ii) If not, then compare the middle element with the search value,
(iii) If the search element is greater than the number in the middle index, then select the elements to the right side of the middle index, and go to Step-1
(iv) If the search element is less than the number in the middle index, then select the elements to the left side of the middle index, and start with Step-1 ( When a match is found, display success message with the index of the element matched.
(vi) If no match is found for all comparisons, then display unsuccessful message

(i) Traverse the array using 'for loop'
(ii) In every iteration, compare the target search key value with the current value of the list.
(iii) If the values match, display the current index and value of the array
(iv) If the values do not match, move on to the next array element
(v) If no match is found, display the search element not found.

(i) A space-time or time-memory trade off is a way of solving in less time by using more storage space or by solving a given algorithm in very little space by spending more time.
(ii) To solve a given programming problem, many different algorithms may be used. Some of these algorithms may be extremely time-efficient and others extremely spaceefficient.
(iii) Time/space trade off refers to a situation where you can reduce the use of memory at the cost of slower program execution, or reduce the running time at the cost of increased memory usage.

Search	To search an item in a data structure using linear and binary search.
Sort	To sort items in a certain order using the methods such as bubble sort, insertion sort, selection sort, etc.
Insert	To insert an item (s) in a data structure.
Update	To update an existing item (s) in a data structure.
Delete	To delete an existing item (s) in a data structure.

Asymptotic Notations are languages that uses meaningful statements about time and space complexity. The following three asymptotic notations are mostly used to represent time complexity of algorithms:
(i) Big O: Big O is often used to describe the worst -case of an algorithm.
(ii) Big \(\Omega \):Big Omega is the reverse Big O, if Big O is used to describe the upper bound (worst - case) of a asymptotic function, Big Omega is used to describe the lower bound (best -case).
(iii) Big \(\Theta \):When an algorithm has complexity with lower bound = upper bound, Say that an algorithm has a complexity O(n log n) and \(\Omega \) (n log n), it's actually has the complexity \(\Theta \) (n log n), which means the running time of that algorithm always falls in n log n in the best-case and worst-case.

(i) Time Factor -Time is measured by counting the number of key operations like comparisons in the sorting algorithm.
(ii) Space Factor -Space is measured by the maximum memory space required by the algorithm.

(i) Input
(ii) Output
(iii) Finiteness
(iv) Definiteness
(v) Effectiveness
(vi) Correctness
(vii) Simplicity
(viii) Unambiguous
(ix) Feasibility
(x) Portable
(xi) Independent

(i) Insertion sort is a simple sorting algorithm. It works by taking elements from the list one by one and inserting then in their correct position in to a new sorted list.
(ii) This algorithm builds the final sorted array at the end. This algorithm uses n-1 number of passes to get the final sorted list as per the pervious algorithm as we have discussed.
Pseudo for Insertion sort:
Step 1 - If it is the first element, it is already sorted.
Step 2 - Pick next element
Step 3 - Compare with all elements in the sorted sub-list
Step 4 - Shift all the elements in the sorted sublist that is greater than the value to be sorted Step 5 - Insert the value Step 6 - Repeat until list is sorted.

(i) The selection sort is a simple sorting algorithm that improves on the performance of bubble sort by making only one exchange for every pass through the list.
(ii) This algorithm will first find the smallest elements in array and swap it with the element in the first position of an array, then it will find the second smallest element and swap that element with the element in the second position, and it will continue until the entire array is sorted in respective order.
(iii) This algorithm repeatedly selects the next smallest element and swaps in into the right place for every pass. Hence it is called selection sort.
Pseudo code:
(i) Start from the first element i.e., index-(), we search the smallest element in the array, and replace it with the element in the first position.
(ii) Now we move on to the second element position, and look for smallest element present in the sub-array, from starting index to till the last index of sub - array.
(iii) Now replace the second smallest identified in step-2 at the second position in the or original array, or also called first position in the sub array.
(iv) This is repeated, until the array is completely sorted.
(v) Let's consider an array with values {13, 16, 11, 18, 14, 15}
(vi) Below, we have a pictorial representation of how selection sort will sort the given array respective order.

(i) In the first pass, the smallest element will be 11, so it will be placed at the first position.
(ii) After that, next smallest element will be searched from an array.
(iii) Then leaving the first element, next smallest element will be searched. It get 13 as smallest, so it will be placed at the second position.
(iv) Then leaving 11 and 13. It will search for the next smallest element and put it at third position and keep doing this until array is sorted.
(v) Finally, it will get the sorted array end of the pass.

(i) Computer resources are limited that should be utilized efficiently. The efficiency of an algorithm is defined as the number of computational resources used by the algorithm.
(ii) An algorithm must be analyzed to determine its resource usage. The efficiency of an algorithm can be measured based on the usage of different resources.
(iii) For maximum efficiency of algorithm we wish to minimize resource usage. The important resources such as time and space complexity cannot be compared directly, so time and space complexity could be considered for an algorithmic efficiency.
Method for determining Efficiency:
(i) The efficiency of an algorithm depends on how efficiently it uses time and memory space.
(ii) The time efficiency of an algorithm is measured by different factors. For example, write a program for a defined algorithm, execute it by using any programming language, and measure the total time it takes to run.
(iii) The execution time that you measure in this case would depend on a number of factors such as: -
1. Speed of the machine
2. Compiler and other system Software tools
3. Operating System
4. Programming language used
5. Volume of data required
(iv) However, to determine: how efficiently an algorithm solves a given problem, you would like to determine how the execution time is affected by the nature of the algorithm.
(v) Therefore, we need to develop fundamental laws that determine the efficiency of a program in terms of the nature of the underlying algorithm.

Suppose A is an algorithm and n is the size of input data, the time and space used by the algorithm A are the two main factors, which decide the efficiency of A.
(i) Time Factor: Time is measured by counting the number of key operations like comparisons in the sorting algorithm.
(ii) Space Factor: Space is measured by the maximum memory space required by the algorithm. The complexity of an algorithm f (n) gives the running time and/or the storage space required by the algorithm in terms of n as the size of input data.
(iii) Time Complexity: The Time complexity of an algorithm is given by the number of steps taken by the algorithm to complete the process.
(iv) Space Complexity: Space complexity of an algorithm is the amount of memory required to run to its completion. The space required by an algorithm is equal to the sum of the following two components:
A fixed part is defined as the total space required to store certain data and variables for an algorithm. For example, simple variables and constants used in an algorithm.
A variable part is defined as the total space required by variables, which sizes depends on the problem and its iteration. For example: recursion used to calculate factorial of a given value n.

(i) Dynamic programming is an algorithmic design method that can be used when the solution to a problem can be viewed as the result of a sequence of decisions.
(ii) Dynamic programming approach is similar to divide and conquer. The given problem is divided into smaller and yet smaller possible sub-problems.
(iii) Dynamic programming is used whenever problems can be divided into similar subproblems. so that their results can be reused to complete the process.
(iv) Dynamic programming approaches are used to find the solution in optimized way. For every inner subproblem, dynamic algorithm will try to check the results of the previously solved sub-problems.
(v) The solutions of overlapped sub-problems are combined in order to get a better solution.
Steps to doDynamic programming :
(i) The given problem will be divided into smaller overlapping sub-problems.
(ii) An optimum solution for the given problem can be achieved by using result of smaller sub-problem.
(iii) Dynamic algorithms uses Memoization
Fibonacci Series - An example :
(i) Fibonacci series generates the subsequent number by adding two previous numbers. Fibonacci series starts from two numbers -Fib 0 & Fib 1. The initial values of Fib 0 & Fib l can be taken as 0 and 1.
(ii) Fibonacci series satisfies the following conditions:
Fibn = Fib_a-1 + Fib_a-2
(iii) Hence, a Fibonacci series for the n value 8 can look like this
Fib₈ = 0 1 1 2 3 5 8 13
Fibonaeci Iterative Algorithm with Dynamic programning approach : The following example shows a simple Dynamic programning approach for the generation ot Fibonacci series.
Initialize f0 = 0, f1 = 1.
Step- 1: Print the initial values of Fibonacci f0 and f1 
Step- 2: Calculate Fibonacci fib \(\leftarrow \) f0+ f1 
Step- 3: Assign f0 \(\leftarrow \) f1, f1 \(\leftarrow \) fib
Step- 4: Print the next consecutive value of Fibonacci fib
Step- 5: Go to step-2 and repeat until the specified number of terms generated
Example:
if we generate Fibonacci series up to 10 digits, the algorithm will generate the series as shown below:
The Fibonacci series is:
0 1 1 2 3 5 8 13 21 34 55.

(i) Linear search also called sequential search is a sequential method for finding a particular value in a list.
(ii) This method checks the search element with each element in sequence until the desired element is found or the list is exhausted. In this searching algorithm, list need not be ordered.
procedure :
1. Traverse the array using for loop
2. In every iteration, compare the target search key value with the current value of the list.
(i) If the values do not match, move on to the next array element.
(ii) If the values match, display the current index and value of the array.
3. If no match is found, display the search element not found.
(iii) To search the number 25 in the array given below, a linear search will go step by step in a sequential order starting from the first element in the given array if the search element is found that index is returned otherwise the search is continued till the last index of the array. In this example number 25 is found at index number 3.

index	0	1	2	3	4
values	10	12	20	25	30

Example 1:
Input: values[] = {5, 34, 65, 12, 77, 35)
target = 77
Output: 4
Example 2:
Input: values[] = [101, 392, 1, 54, 32, 22, 90, 93) target = 200
Output: -1 (not found)

 

Input	Zero or more quantities to be supplied.
Output	At least one quantityis produced.
Finiteness	Algorithms must terminate after finite number of steps.
Definiteness	All operations should be well defined. For example operations involving division by zero or taking square root for negative number are unacceptable.
Effectiveness	Every instruction must be carried out effectively.
Correctness	The algorithms should be error free.
Simplicity	East to implement.
Unambiguous	Algorithm should be clear and unambiguous. Each of its steps and their inputs/outputs should be clear and must lead to only one meaning.
Feasibility	Should be feasible with the avaliable resources.
Portable	An algorithm should be generic, independent of any programming language or an operating system able to handle all range of inputs.
Independent	An algorithm should have step-by-step directions, which should be independent of any programming code.