B.
Sathis Kumar VIT CC
Algorithms and problem-solving
Problem-solving strategies The role of algorithms in the problem-solving process Implementation strategies for algorithms Debugging strategies The concept and properties of algorithms Learning outcomes: 1. Discuss the importance of algorithms in the problem-solving process. 2. Identify the necessary properties of good algorithms. 3. Create algorithms for solving simple problems. 4. Use pseudocode or a programming language to implement, test, and debug algorithms for solving simple problems. 5. Describe strategies that are useful in debugging.
B.Sathis Kumar VIT CC
What is a Problem
A state of difficulty that needs to be resolved PROBLEMS EXIST WHERE GOALS NEED TO BE ATTAINED AND THERE IS UNCERTAINTY ABOUT SOLUTION
B.Sathis Kumar VIT CC
Problem faced everyday life
People make decisions everyday Examples: Should I wear casual or formal today? Should I watch TV or go out to cinema? what career? what course? What shoes? Everything needs a DECISION AS A SOLUTION TO THE PROBLEM
B.Sathis Kumar VIT CC
What happens when bad decisions are made?
WASTAGE OF TIME AND RESOURCES
B.Sathis Kumar VIT CC
Types of Problems
Research Problems Knowledge Problems Troubleshooting Problems Mathematics Problems Resource Problems Social Problems Design Problems
B.Sathis Kumar VIT CC
Types of Problems
Research Problems
A hypothesis be proven or disproved Example; CFC may destroy the earths ozone layer is a hypothesis. Design an experiment that either proves or disproves the hypothesis
B.Sathis Kumar VIT CC
Types of Problems
Research Problems Knowledge Problems Troubleshooting Problems Mathematics Problems Resource Problems Social Problems Design Problems
B.Sathis Kumar VIT CC
Types of Problems
Research Problems
A hypothesis be proven or disproved Example; CFC may destroy the earths ozone layer is a hypothesis. Design an experiment that either proves or disproves the hypothesis
B.Sathis Kumar VIT CC
Types of Problems; cont
Knowledge Problems
When a person encounters a situation that he doesnt understand Example; A chemical engineer noticed that the chemical plant produces more product when it rains Further study showed that heat exchanger cooled by rain increasing product
B.Sathis Kumar VIT CC
Types of Problems; cont
Troubleshooting Problems; cont e.g. an electronic amplifier has a loud hum when it is in a room with fluorescent lights.
B.Sathis Kumar VIT CC
Types of Problems; cont
Mathematics Problems
Describe physical phenomena with mathematical models Engineers can unleash the extraordinary power of mathematics, with the rigorously proven theorems and algorithms Example; Isaac Newtons sine square law can be applied to hypersonic flow e.g. find x such that 4x + 5 = 0.
B.Sathis Kumar VIT CC
Types of Problems
Resource Problems
There is never enough time, money, or equipment to accomplish the task Engineers who can get the job done in spite of resource limitations are highly prized and awarded e.g. how will we get the money to build our new factory?
B.Sathis Kumar VIT CC
Types of Problems
Social Problems
For example, if a factory is relocated to where there is shortage of skilled worker, engineers should set up training program for employees e.g. how can we improve education?
B.Sathis Kumar VIT CC
Types of Problems
Design Problems
Require creativity, teamwork, and broad knowledge Example; design a new car Economy car? Sports Utility Vehicle ? Design goal and parameters
B.Sathis Kumar VIT CC
Practical Examples
Internet and Networks
The need to access large amount of information with the shortest time. Problems of finding the best routs for the data to travel. Algorithms for searching this large amount of data to quickly find the pages on which particular information resides.
Electronic Commerce
The ability of keeping the information (credit card numbers, passwords, bank statements) private, safe, and secure. Algorithms involves encryption/decryption techniques.
B.Sathis Kumar VIT CC
16
What is Problem Solving?
According to Michael E. Martinez There is no formula for problem solving How people solve problems varies Mistakes are inevitable Problem solvers need to be aware of the total process Flexibility is essential Error and uncertainty should be expected
B.Sathis Kumar VIT CC
Six steps to ensure a Best decision in PROBLEM SOLVING
Identify the problem Understand the problem Identify alternative ways to solve the problem Select the best way to solve the problem from the list of alternative solutions List instructions that enable you to solve the problem using selected solution Evaluate the solution
B.Sathis Kumar VIT CC
Approaches to solve a problem:
Algorithmic Heuristic
Important definitions Solutions that can be solved with a series of known actions are called Algorithmic Solutions Employing a self-learning approach to the solution of a problems is known as Heuristic Solutions
B.Sathis Kumar VIT CC
Examples
Algorithmic solution: To make a cup of coffee To find largest of three numbers Heuristic solutions: how to buy the best stock? How to play chess?
B.Sathis Kumar VIT CC
Computer Problem Solving Process
Step 1 - Analyze the problem
Outline the problem and its requirements Design steps (algorithm) to solve the problem
Step 2 - Implement the algorithm
Implement the algorithm in code Verify that the algorithm works
Step 3 - Maintenance
Use and modify the program if the problem domain changes
B.Sathis Kumar VIT CC
Computer Problem-Solving
The computer problem-solving process
B.Sathis Kumar VIT CC
Analyze the Problem
Thoroughly understand the problem Understand problem requirements
Does program require user interaction? Does program manipulate data? What is the output?
If the problem is complex, divide it into subproblems
Analyze each subproblem as above
B.Sathis Kumar VIT CC
Algorithm:
is a systematic procedure that produces - in a finite number of steps - the answer to a question or the solution of a problem. is a sequence of instructions which can be used to solve a given problem
B.Sathis Kumar VIT CC
What is an algorithm?
Before a computer can perform a task, it must have an algorithm that tells it what to do. Informally: An algorithm is a set of steps that define how a task is performed. Formally: An algorithm is an ordered set of unambiguous executable steps, defining a terminating process. Ordered set of steps: structure! Executable steps: doable! Unambiguous steps: follow the directions! Terminating: must have an end (solution)
B.Sathis Kumar VIT CC
Three Requirements
1.
Sequence is:
a. b.
Precise Consists of a limited number of steps
2.
Each step is:
a. b.
Unambiguous Executable
3.
The sequence of steps terminates in the form of a solution
B.Sathis Kumar VIT CC
Origin of the Term Algorithm
The name derives from the title of a Latin book: Algoritmi de numero Indorum That book was a translation of an Arabic book: Al-Khwarizmi Concerning the Hindu Art of Reckoning That book was written by the famous 9-th century Muslim mathematician, Muhammad ibn Musa al-Khwarizmi
B.Sathis Kumar VIT CC
What is an algorithm?
B.Sathis Kumar VIT CC
Properties of Algorithm
An Algorithm has five properties as follows: Finiteness: An algorithm should end in a finite number of steps. Definiteness: Every step of an algorithm should be clear and unambiguously defined. Input: The input of an algorithm can either be given interactively by the user or generated internally. Output: An algorithm should have at least one output. Effectiveness: Every step in the algorithm should be easy to understand
B.Sathis Kumar VIT CC
Expressing Algorithms
Algorithms can be expressed in many kinds of notation, including
Natural Languages Pseudocode Flowcharts Programming Languages
B.Sathis Kumar VIT CC
Expressing Algorithms
English description
More More easily expressed
Pseudo-code
precise
High-level programming language
B.Sathis Kumar VIT CC
Natural Languages Can algorithms be represented in Natural Languages? Natural language expressions of algorithms tend to be verbose and ambiguous, and are rarely used for complex or technical algorithms Pseudocode & Flowcharts Pseudocode and flowcharts are structured ways to express algorithms that avoid many of the ambiguities common in natural language statements, while remaining independent of a particular implementation language Generally, flowcharts work well for small problems but Pseudocode is used for larger problems. Programming Languages Programming languages are primarily intended for expressing algorithms in a form that can be executed by a computer, but are often used as a way to define or document algorithms.
B.Sathis Kumar VIT CC
Example
B.Sathis Kumar VIT CC
Pseudo Code
An algorithm is independent of any language or machine whereas a program is dependent on a language and machine To fill the gap between these two, we need pseudo codes Psuedo-code is a way to represent the step by step methods in finding the solution to the given problem.
B.Sathis Kumar VIT CC
Pseudocode
Pseudocode is like a programming language, but not as rigid Written as a combination of English and programming constructs
Based on selection (if, switch) and iteration (while, repeat) constructs in high-level programming languages
Design using these high level primitives
Independent of actual programming language
B.Sathis Kumar VIT CC
Example:
Algorithm arrayMax (A,n) 1.Input array A of n integers 2.CurrentMax = A[0] 3.for i = 1 to n do if A[i] > currentMax then currentMax = A[i] 4.return currentMax
B.Sathis Kumar VIT CC
Computer operations in Pseudocode/Components of Algorithm
Read
1. Input Data
Read student name
Get
Get student name
B.Sathis Kumar VIT CC
Computer operations in Pseudocode/Components of Algorithm
2. Output Information
Print Print Program Complete Write Write record to file Output Output totalAmount Display Display Program Complete
B.Sathis Kumar VIT CC
Computer operations in Pseudocode/Components of Algorithm
3. Perform Arithmetic
Add Add num1 to num2 Subtract Subtract num1 from num2 Multiply Multiply num1 by num2 Divide Divide num1 by num2
B.Sathis Kumar VIT CC
Computer operations in Pseudocode/Components of Algorithm
4. Assign Values
Initialise Initialise totalPrice to zero Set Set totalPrice to zero Store Store zero in totalPrice
B.Sathis Kumar VIT CC
Computer operations in Pseudocode/Components of Algorithm
5. Compare Values
IFTHENELSE IF num1 > num 2 THEN ADD num1 to toal ELSE ADD num2 to total ENDIF
B.Sathis Kumar VIT CC
Computer operations in Pseudocode/Components of Algorithm
6. Repeat Actions
DOWHILE
DOWHILE Num1 > Num2 ADD num1 to total Multiply total by 3 Subtract Num2 by 3 ENDDO
B.Sathis Kumar VIT CC
Form of an Algorithm Control Module 1. Instruction 2. Instruction 3. 4. .. .. ---end
Note: Uses End indicating end of processing
Name of Module (list of Parameters) 1. Instruction 2. Instruction 3. .. 4. .. .. ..exit
Note: Uses Exit bcos processing continues
B.Sathis Kumar VIT CC
Biggest of Two Numbers
B.Sathis Kumar VIT CC
Biggest of Two Numbers
B.Sathis Kumar VIT CC
Pseudocode (Contd)
Example: The sequential search algorithm in pseudocode
B.Sathis Kumar VIT CC
Flowchart
A graphical representation of a process (e.g. an algorithm), in which graphic objects are used to indicate the steps & decisions that are taken as the process moves along from start to finish. Individual steps are represented by boxes and other shapes on the flowchart, with arrows between those shapes indicating the order in which the steps are taken.
B.Sathis Kumar VIT CC
FLOW CHART SYMBOLS
Start or stop Process Input or output Decision Flow line Connector Off-page connector
B.Sathis Kumar VIT CC
FLOW CHART SYMBOLS
Flowchart Symbols
Process Module
counter
Automaticcounter loop
A S
B.Sathis Kumar VIT CC
Two main issues related to algorithms
How to design algorithms
How to analyze algorithm efficiency
B.Sathis Kumar VIT CC
Analysis of Algorithms
An algorithm when implemented, uses the computers primary memory and Central Processing Unit Analyzing the amount of resources needed for a particular solution of the problem The Analysis is done at two stages: Priori Analysis: Analysis done before implementation Posteriori Analysis: Analysis done after implementation
B.Sathis Kumar VIT CC
Eg. Algorithm to check whether a number is prime or not. Algo1: Divide the number n from 2 to (n-1) and check the reminder Algo2: Divide the number n from 2 to n/2 and check the reminder Algo3: Divide the number n from 2 to sqrt(n) and check the reminder
B.Sathis Kumar VIT CC
Before implementing the algorithm (Priori Analysis) in a programming language, the best of the three algorithms will be selected(Algo3 will suit if n is large). After implementing the algorithm (Posteriori Analysis) in a programming language, the performance is checked with the help of a profiler.
B.Sathis Kumar VIT CC
Analysis of Algorithms
Refers to predicting the resources required by the algorithm, based on size of the problem The primary resources required are Time and Space Analysis based on time taken to execute the algorithm is called Time complexity of the Algorithm Analysis based on the memory required to execute the algorithm is called Space complexity of the Algorithm
B.Sathis Kumar VIT CC
Space Complexity
The space needed by a program has the following components: Instruction space: Space needed to store the object code. Data space: Space needed to store constants & variables. Environment stack space: Space needed when functions are called. If the function, fnA calls another function fnB then the return address and all the local variables and formal parameters are to stored.
B.Sathis Kumar VIT CC
Time Complexity
Time complexity depends on the machine, compilers and other real time factors. Total time = ( ti * opi(n) ) Where opi(n) is the number of instances the operation opi occurs and ti is the time taken for executing the operation This Total time is a varying factor which depends on the current load of the system and other real time factors like communication
B.Sathis Kumar VIT CC
The running time of an algorithm is influenced by several factors:
Speed of the machine running the program Language in which the program was written. For example, programs written in assembly language generally run faster than those written in C or C++, which in turn tend to run faster than those written in Java. Efficiency of the compiler that created the program The size of the input: processing 1000 records will take more time than processing 10 records. Organization of the input: if the item we are searching for is at the top of the list, it will take less time to find it than if it is at the bottom.
B.Sathis Kumar VIT CC
T(n), or the running time of a particular algorithm on input of size n, is taken to be the number of times the instructions in the algorithm are executed. Pseudo code algorithm illustrates the calculation of the mean (average) of a set of n numbers:
1. n = read input from user 2. sum = 0 3. i =1 4. while i <= n 5. number = read input from user 6. sum = sum + number 7. i = i + 1 8. mean = sum / n
The computing time for this algorithm in terms on input size n is: T(n) = 4n + 5.
Statement 1 2 3 4 5 6 7 8
Number of times executed 1 1 1 n+1 n n n 1
B.Sathis Kumar VIT CC
Time Complexity example
1.2 contains one condition checking and one increment. Each will be done for (n+1) times, so 2*(n+1)= 2n+2
B.Sathis Kumar VIT CC
Recursive functions Time complexity
B.Sathis Kumar VIT CC
Complexity (Efficiant Calculation)
Comparison: time complexity of algorithms A and B
Input Size n 10 100 1,000 1,000,000
Algorithm A 5,000n 50,000 500,000 5,000,000 5109
Algorithm B 1.1n 3 13,781 2.51041 4.81041392
B.Sathis Kumar VIT CC
Complexity
This means that algorithm B cannot be used for large inputs, while running algorithm A is still feasible. So what is important is the growth of the complexity functions. The growth of time and space complexity with increasing input size n is a suitable measure for the comparison of algorithms.
B.Sathis Kumar VIT CC
Analysis based on the nature of the problem
The analysis of the algorithm can be performed based on the nature of the problem. Thus we have: Worst case analysis Average case analysis Best case analysis
B.Sathis Kumar VIT CC
Algorithms can be analyzed in many dimensions, speed, accuracy, power consumption, and resiliency. Numerical algorithms have to be devised for adequate accuracy. Only after you get sufficient accuracy can we look at speed. Speed has many dimensions, asymptotic, mean time, variance of the execution time, etc. Memory or in general resource usage is a dual metric Embedded systems have to be power efficient, e.g. cell phones. Many algorithms, especially banking and finance are required to be fault tolerant, especially of server failures, etc. These systems are required to be generally geographically distributed. .
B.Sathis Kumar VIT CC
Efficiency Measures
Performance of a solution Most of the software problems do not have a single best solution Then how do we judge these solutions? The solutions are chosen based on performance measures Performance Measures Time Quality Simplicity
B.Sathis Kumar VIT CC
Some algorithms are harder than others
Some algorithms are easy
Finding the largest (or smallest) value in a list Finding a specific value in a list
Some algorithms are a bit harder
Sorting a list
Some algorithms are very hard
Finding the shortest path between two cities
Some algorithms are essentially impossible
Factoring large composite numbers
B.Sathis Kumar VIT CC
Analysis based on the nature of the problem
Worst case: Under what condition/s does the algorithm when executed consumes maximum amount of resources. It is the maximum amount of resource the algorithm can consume for any value of problem size. Best case: Under what condition/s does the algorithm when executed consumes minimum amount of resources. Average case: Average case analysis is done by considering every possibility are equally likely to happen.
B.Sathis Kumar VIT CC
Hard problems
We can identify the Efficiency of an algorithm from its speed (how long does the algorithm take to produce the result). Some problems have unknown efficient solution. These problems are called NP-complete problems. If we can show that the problem is NP-complete, we can spend our time developing an efficient algorithm that gives a good, but not the best possible solution.
B.Sathis Kumar VIT CC
68
Some Basic Mathematics
Mathematical knowledge is an essence for performing priori analysis. Arithmetic progressions: In this series, the difference between an element to its successor is the same as the difference between the element and its predecessor. So the series will be, a, a + d, a + 2d, a + 3d, Sum of n terms = n/2 * ( first term + last term)
B.Sathis Kumar VIT CC
Introduction to Logarithms
In its simplest form, a logarithm answers the question: How many of one number do we multiply to get another number? Example How many 2s do we multiply to get 8? Answer: 2 2 2 = 8, so we needed to multiply 3 of the 2s to get 8 So the logarithm is 3
B.Sathis Kumar VIT CC
How to Write it
We would write "the number of 2s you need to multiply to get 8 is 3" as log2(8) = 3 So these two things are the same:
The number we are multiplying is called the "base", so we would say: "the logarithm of 8 with base 2 is 3" or "log base 2 of 8 is 3" or "the base-2 log of 8 is 3"
B.Sathis Kumar VIT CC
Notice we are dealing with three numbers: the base: the number we are multiplying (a "2" in the example above) how many times to use it in a multiplication (3 times, which is the logarithm) The number we want to get (an "8")
B.Sathis Kumar VIT CC
More Examples
Example: What is log5(625) ... ? We are asking "how many 5s need to be multiplied together to get 625?
B.Sathis Kumar VIT CC
Answer:
5 5 5 5 = 625, so we need 4 of the 5s Answer: log5(625) = 4
B.Sathis Kumar VIT CC
Example: What is log2(64) ... ? We are asking "how many 2s need to be multiplied together to get 64?"
B.Sathis Kumar VIT CC
2 2 2 2 2 2 = 64, so we need 6 of the 2s Answer: log2(64) = 6
B.Sathis Kumar VIT CC
Exponents
Exponents and Logarithms are related, let's find out how ... The exponent says how many times to use the number in a multiplication. In this example: 23 = 2 2 2 = 8 (2 is used 3 times in a multiplication to get 8)
B.Sathis Kumar VIT CC
So when you have a question like this:
The Logarithm answers it like this:
The logarithm tell you what the exponent is!
B.Sathis Kumar VIT CC
the general case is: Example: What is log10(100) ... ? 102 = 100 So an exponent of 2 is needed to make 10 into 100, and: log10(100) = 2 Example: What is log3(81) ... ? 34 = 81 So an exponent of 4 is needed to make 3 into 81, and: log3(81) = 4
B.Sathis Kumar VIT CC
Note: Whenever the log is specified, it is log base 2.
B.Sathis Kumar VIT CC
A few mathematical formulae.
B.Sathis Kumar VIT CC
In the figure in the slide, the x axis represents the problem size and the y axis represents the resources
B.Sathis Kumar VIT CC
Growth of function
B.Sathis Kumar VIT CC
Generalizing Running Time
Comparing the growth of the running time as the input grows to the growth of known functions.
Input Size: n 5 10 100
log n
n log n
3 4 7
5 10 100
15 33 664
25 100 104
125 10 106
32 10 1030
1000 10000
10 13
1000
104
106 108
109 1012
10300 103000
10000 Kumar VIT CC 105 B.Sathis
Order of Magnitude of an algorithm
Calculate the running time and consider only the leading term of the formula which gives the order of magnitude. Example 1 for( i = 0; i< n; i ++) { ... ... } Assume there are c number of statements inside the loop Each statement takes 1 unit of time Execution time for 1 loop = c * 1 = c Total execution time = n * c Since c is constant it is insignificant. So the order is n
B.Sathis Kumar VIT CC
Order of Magnitude of an algorithm
In calculating the order of magnitude, the lower order terms are left out as they are relatively insignificant. The assumptions in the example are made because we will not know on which machine the algorithm is to be implemented. So we cant exactly say how much time each statement will take. The exact time depends on the machine on which the algorithm is run. In the example the approximation is done because for higher values of n, the effect of c (constant) will not be significant. Thus, constants can be ignored.
B.Sathis Kumar VIT CC
Order of Magnitude of an algorithm
for( i=0;i<n; i ++) { for(j=0;j<m;j++) { . . } } Assume we have c number of statements inside the innermost loop Following the same assumptions as the earlier example Execution time for 1 loop = c * 1 Execution time for the inner loop = m * c Total execution time = n * (m * c) Since c is a constant, the total execution time = n * m
B.Sathis Kumar VIT CC
Analysis based on the nature of the problem
The analysis of the algorithm can be performed based on the nature of the problem. Thus we have: Worst case analysis Average case analysis Best case analysis
B.Sathis Kumar VIT CC
Worst case:
Under what condition/s does the algorithm when executed consumes maximum amount of resources. It is the maximum amount of resource the algorithm can consume for any value of problem size.
B.Sathis Kumar VIT CC
Best case:
Under what condition/s does the algorithm when executed consumes minimum amount of resources.
B.Sathis Kumar VIT CC
Average case:
This is between worst case & best case. It is probabilistic in nature. Average-case running times are calculated by first arriving at an understanding of the average nature of the input, and then performing a running-time analysis of the algorithm for this configuration. Average case analysis is done by considering every possibility are equally likely to happen.
B.Sathis Kumar VIT CC
Why Worst case analysis?
Even though the average case is more tends towards the real situation worst case analysis is preferred due to the following reasons: It is better to bound ones pessimism the time of execution cant go beyond T(n) as it is the upper bound Generally it is easy to compute the worst case analysis as compared to computation of best case and average case of algorithms
B.Sathis Kumar VIT CC
Asymptotic notations for determination of order of magnitude of an algorithm
The limiting behavior of the complexity of a problem as problem size increases is called asymptotic complexity The most common asymptotic notations are: Big Oh ( O) notation: It represents the upper bound of the resources required to solve a problem. It is represented by O For example Upper bound is also called the upper limit or the range of maximum values. Eg: when we consider marks of a student out of 100, 100 is the upper bound. Student cant get marks greater than 100. Omega notation: It represents the lower bound of the resources required to solve a problem. It is represented by
B.Sathis Kumar VIT CC
Big Oh Vs Omega notations
Case (i) : A Project manager requires maximum of 100 software engineers to finish the project on time. Case (ii) : The Project manager can start the project with minimum of 50 software engineers but cannot assure the completion of project in time. Which case is preferred? Case (i) is preferred in most of the situations
B.Sathis Kumar VIT CC
Case (i) is similar to Big Oh notation, specifying the upper bound of resources needed to do a task. Case (ii) is similar to Omega notation, specifying the lower bound of resources needed to do a task.
B.Sathis Kumar VIT CC
Big Oh manipulations
While finding the worst case complexities of algorithms using Big Oh notation, some/all of the following rules are used. Rule I all lower powers of n and the constants are ignored in f(n) The constants and the slower growing terms are ignored as their growth rates are insignificant compared to the growth rate of the highest power.
B.Sathis Kumar VIT CC
Rule II :
The time of execution of a for loop is the running time of all statements inside the for loop multiplied by number of iterations of the for loop. Example: for( i=0 to n) { x= x + 1; y= y + 1; x= x + y } The for loop is executed n times. So, worst case running time of the algorithm is T ( n ) = O( 3 * n ) = O ( n )
B.Sathis Kumar VIT CC
Rule III :
If we have a nested for loop, in an algorithm, the analysis of that algorithm should start from the inner loop and move it outwards towards outer loop. Example: for(j=0 to m) { for( i=0 to n) { X= x + 1; y = y + 1; z = x + y; } } The worst case running time of inner loop is O( 3*n ) The worst case running time of outer loop is O( m*3*n ) The total running time = O ( m * n )
B.Sathis Kumar VIT CC
Rule IV :
The execution of an if else statement is an algorithm comprises of Execution time for testing the condition The maximum execution time of either if or else( whichever is larger ) Example: If(x > y) { print( x is larger than y); print( x is the value to be selected); z= x; x= x+1; } else { print( x is smaller than y); } The execution time of the program is the exec. time of testing (X > Y) +exec. time of if statement, as the execution time of if statement is more than that of else statement
B.Sathis Kumar VIT CC
Case study on analysis of algorithms
The following examples will help us to understand the concept of worst case and average case complexities Example 1: Consider the following pseudocode. To insert a given value, k at a particular index, l in an array, a[1n]: 1. Begin 2. Copy a[ln] to a[l+1n+1] (Assuming space is available) 3. Copy k to a[l] 4. End
B.Sathis Kumar VIT CC
The above given code inserts a value k into position l in an array a. The basic operation here is copy. Worst Case Analysis: Step 2 does n copies in the worst case. Step 3 does 1 copy. So the total number of copy operations is n+1=n+1. Hence the worst case complexity of array insertion is O(n). Best case Analysis: O(1) = 1, as only one insertion is done with no movements.
B.Sathis Kumar VIT CC
Average Case Analysis: On an average step 2 will perform (n-1)/2 copies. This is derived as follows: The probability that step 2 performs 1 copy is 1/n, the probability that it performs 2 copies is 2/n and so on. The probability that it performs n-1 copies is (n-1)/n. Hence the average number of copies that step 2 performs is (1/n) + (2/n) + + (n-1)/n + (n/n) = (n+1)/2. Also step 3 performs 1 copy. So on an average the array insertion performs ((n+1)/2) + 1 copies. Hence the average case complexity of array insertion is O(n).
B.Sathis Kumar VIT CC
Example 2:
To delete the value, k at a given index, i in an array, a[1n]:
B.Sathis Kumar VIT CC
The above given code deletes the value k at a given index i in an array a. The basic operation here is copy. Worst Case Analysis: Step 2 does n-1 copies in the worst case. So the total number of copy operations is n-1. Hence the worst case complexity is O(n). Best case Analysis: O(1) = 1, as only one deletion will be done with no further movements
B.Sathis Kumar VIT CC
Average Case Analysis:
On an average step 2 will perform (n-1)/2 copies. This is derived as follows: The probability that step 2 performs 1 copy is 1/n, the probability that it performs 2 copies is 2/n and so on. The probability that it performs n-1 copies is (n-1)/n. Hence the average number of copies that step 2 performs is (1/n) + (2/n) + + (n-1)/n = (n-1)/2. So on an average the array deletion performs ((n-1)/2) copies. Hence the average case complexity of array insertion is O(n).
B.Sathis Kumar VIT CC
B.Sathis Kumar VIT CC
