Question

In: Computer Science

Algorithmic Performance as you are aware, consists (mainly) of 2 dimensions: Time and Space. From a...

Algorithmic Performance as you are aware, consists (mainly) of 2 dimensions: Time and Space. From a technical perspective, discuss the following:  Regarding runtime, discuss algorithmic performance with respect to its runtime performance. As you develop an algorithm, what must you also consider in terms of some of the trade-offs? How would you go about estimating the time required for an algorithm’s efficiency (i.e. time to complete in terms of its potential complexity)? What techniques can you use? Give an example of how to measure it.

Solutions

Expert Solution

runtime:

Runtime is the period of time when a program is running. It begins when a program is opened (or executed) and ends with the program is quit or closed. Runtime is a technical term, used most often in software development.

Runtime describes software/instructions that are executed while your program is running, especially those instructions that you did not write explicitly, but are necessary for the proper execution of your code.

Low-level languages like C have very small (if any) runtime. More complex languages like Objective-C, which allows for dynamic message passing, have a much more extensive runtime.

You are correct that runtime code is library code, but library code is a more general term, describing the code produced by any library. Runtime code is specifically the code required to implement the features of the language itself.

Runtime is a general term that refers to any library, framework, or platform that your code runs on.

The C and C++ runtimes are collections of functions.

The .NET runtime contains an intermediate language interpreter, a garbage collector, and more.

Performance of algorithm:

By measuring performance of an algorithm we can determine which algorithm is better than the other one. Performance of an algorithm is usually represented by the Big O Notation. Follow along and learn more about measuring performance of an algorithm.

A good algorithm is correct, but a great algorithm is both correct and efficient. The most efficient algorithm is one that takes the least amount of execution time and memory usage possible while still yielding a correct answer.

Counting the operations

One way to measure the efficiency of an algorithm is to count how many operations it needs in order to find the answer across different input sizes.

Let's start by measuring the linear search algorithm, which finds a value in a list. The algorithm looks through each item in the list, checking each one to see if it equals the target value. If it finds the value, it immediately returns the index. If it never finds the value after checking every list item, it returns -1.

Here's what that algorithm looks like in pseudocode:

PROCEDURE searchList(numbers, targetNumber) {
index ← 1
REPEAT UNTIL (index > LENGTH(numbers)) {
IF (numbers[index] = targetNumber) {
RETURN index
}
index ← index + 1
}
RETURN -1
}
Analysis of algorithm is the process of analyzing the problem-solving capability of the algorithm in terms of the time and size required (the size of memory for storage while implementation). However, the main concern of analysis of algorithms is the required time or performance. Generally, we perform the following types of analysis −

Worst-case − The maximum number of steps taken on any instance of size a.

Best-case − The minimum number of steps taken on any instance of size a.

Average case − An average number of steps taken on any instance of size a.

Amortized − A sequence of operations applied to the input of size a averaged over time.

To solve a problem, we need to consider time as well as space complexity as the program may run on a system where memory is limited but adequate space is available or may be vice-versa. In this context, if we compare bubble sort and merge sort. Bubble sort does not require additional memory, but merge sort requires additional space. Though time complexity of bubble sort is higher compared to merge sort, we may need to apply bubble sort if the program needs to run in an environment, where memory is very limited.
Understanding the problem

Before an algorithm can be designed, it is important to check that the problem is completely understood. There are a number of basic things to know in order to really understand the problem:

What are the inputs into the problem?
What will be the outputs of the problem?
In what order do instructions need to be carried out?
What decisions need to be made in the problem?
Are any areas of the problem repeated?
Before designing an algorithm it is important to first understand what the problem is. Algorithms can be designed using pseudocode or a flowchart, and the standard notations of each should be known.

Pseudocode

Most programs are developed using programming languages. These languages have specific syntax that must be used so that the program will run properly. Pseudocode is not a programming language, it is a simple way of describing a set of instructions that does not have to use specific syntax.

Common pseudocode notation

There is no strict set of standard notations for pseudocode, but some of the most widely recognised are:

INPUT – indicates a user will be inputting something
OUTPUT – indicates that an output will appear on the screen
WHILE – a loop (iteration that has a condition at the beginning)
FOR – a counting loop (iteration)
REPEAT – UNTIL – a loop (iteration) that has a condition at the end
IF – THEN – ELSE – a decision (selection) in which a choice is made
any instructions that occur inside a selection or iteration are usually indented
Flowcharts

A flowchart is a diagram that represents a set of instructions. Flowcharts normally use standard symbols to represent the different types of instructions. These symbols are used to construct the flowchart and show the step-by-step solution to the problem.

-When the design of new algorithms is applied in practical terms, the related discipline is known as algorithm engineering. The two functions are frequently carried out by the same people, although larger organizations (such as Amazon and Google) employ specialized designers and engineers, given their level of need for new and specialized algorithms. Like the design process, algorithm engineering frequently involves computer science accreditation, with a strong background in mathematics: where they exist as a separate, specialized profession, algorithm engineers take the conceptual ideas of designers and create processes from them that a computer will understand. With the steady advancement of digital technology, dedicated engineers will continue to become more and more common.

Analysis of efficiency of an algorithm

Analysis of efficiency of an algorithm can be performed at two different stages, before implementation and after implementation, as

A priori analysis − This is defined as theoretical analysis of an algorithm. Efficiency of algorithm is measured by assuming that all other factors e.g. speed of processor, are constant and have no effect on implementation.

A posterior analysis − This is defined as empirical analysis of an algorithm. The chosen algorithm is implemented using programming language. Next the chosen algorithm is executed on target computer machine. In this analysis, actual statistics like running time and space needed are collected.

Algorithm analysis is dealt with the execution or running time of various operations involved. Running time of an operation can be defined as number of computer instructions executed per operation.

Algorithm Complexity

Suppose X is treated as an algorithm and N is treated as the size of input data, the time and space implemented by the Algorithm X are the two main factors which determine the efficiency of X.

Time Factor − The time is calculated or measured by counting the number of key operations such as comparisons in sorting algorithm.

Space Factor − The space is calculated or measured by counting the maximum memory space required by the algorithm.

The complexity of an algorithm f(N) provides the running time and / or storage space needed by the algorithm with respect of N as the size of input data.

Space Complexity

Space complexity of an algorithm represents the amount of memory space needed the algorithm in its life cycle.

Space needed by an algorithm is equal to the sum of the following two components

A fixed part that is a space required to store certain data and variables (i.e. simple variables and constants, program size etc.), that are not dependent of the size of the problem.

A variable part is a space required by variables, whose size is totally dependent on the size of the problem. For example, recursion stack space, dynamic memory allocation etc.

Space complexity S(p) of any algorithm p is S(p) = A + Sp(I) Where A is treated as the fixed part and S(I) is treated as the variable part of the algorithm which depends on instance characteristic I. Following is a simple example that tries to explain the concept

Algorithm

SUM(P, Q)
Step 1 - START
Step 2 - R ← P + Q + 10
Step 3 - Stop
Here we have three variables P, Q and R and one constant. Hence S(p) = 1+3. Now space is dependent on data types of given constant types and variables and it will be multiplied accordingly.

Time Complexity

Time Complexity of an algorithm is the representation of the amount of time required by the algorithm to execute to completion. Time requirements can be denoted or defined as a numerical function t(N), where t(N) can be measured as the number of steps, provided each step takes constant time.

For example, in case of addition of two n-bit integers, N steps are taken. Consequently, the total computational time is t(N) = c*n, where c is the time consumed for addition of two bits. Here, we observe that t(N) grows linearly as input size increases.

IF WE HAVE ANY DOUBTS COMMENT ME thq

give me the positiver rationg


Related Solutions

Java Algorithmic Performance as you are aware, consists (mainly) of 2 dimensions: Time and Space. From...
Java Algorithmic Performance as you are aware, consists (mainly) of 2 dimensions: Time and Space. From a technical perspective, discuss the following: Regarding runtime, discuss algorithmic performance with respect to its runtime performance.  As you develop an algorithm, what must you also consider in terms of some of the trade-offs?    How would you go about estimating the time required for an algorithm’s efficiency (i.e. time to complete in terms of its potential complexity)? What techniques can you use? Give an...
Derive the Dirac gamma matrices for 2-space dimensions and 1-time dimension.
Derive the Dirac gamma matrices for 2-space dimensions and 1-time dimension.
2. Classify each of the following processes as discrete-time or continuous-time, and discrete-space or continuous-space. (a)...
2. Classify each of the following processes as discrete-time or continuous-time, and discrete-space or continuous-space. (a) The baud rate of a modem, recorded every 60 s (b) The number of people logged into Facebook throughout the day (c) The operational state, denoted 1 or 0, of a certain machine recorded at the end of each hour (d) The noise (in dB) in an audio signal measured throughout transmission
Derive the Lorentz transformations for time from the transformations for space.
Derive the Lorentz transformations for time from the transformations for space.
Do you think CITI Bank was aware of the challenges of the internet during that time?...
Do you think CITI Bank was aware of the challenges of the internet during that time? Please discuss what could have been some of the possible risks and opportunities?
describe a time when you had to use attribute analyis in the field. were you aware...
describe a time when you had to use attribute analyis in the field. were you aware of the different analytic tools that you could use? would you do anything different?
How do you think an engineering manager should make an employee aware that their performance is not at the level expected?
How do you think an engineering manager should make an employee aware that their performance is not at the level expected? Do you feel you should have a different approach for your technical/professional employees than you have for other employees?Is there such a thing as "positive criticism"? Give an example to support your answer.How does the application of the "golden rule" relate to the concept of respect? Be specific.Write a "code of personal ethics" which you feel you should follow.Look...
SET 2 By now, you are hopefully aware that there are at least 3 genes (D,...
SET 2 By now, you are hopefully aware that there are at least 3 genes (D, H and I) that work together to determine someone’s blood phenotype. Assume that Tony, whose genotype is DdhhI A i mated with Mary, whose genotype is DdHhI B I B . a) What is the expected phenotypic segregation for their progeny? Show your work and clearly indicate your final answers b) Which of the progeny would be able to receive blood from their mother...
2 (d). Detail any considerations to the activities you may need to be aware of in...
2 (d). Detail any considerations to the activities you may need to be aware of in order to support the client’s cultural and religious needs. 2 (e). Explain the importance of collaboration with the client in situations where barriers are present. 2 (f). Explain how the client’s individualised plan should be used when identifying and implementing activities and services for your client. 2 (g). Document the strategies you used to encourage and assist the inclusion of your client in external...
In this lab, you will implement and evaluate the performance (run time and # of conflicts),...
In this lab, you will implement and evaluate the performance (run time and # of conflicts), for different load factors, of three hashing schemes: • linear, • quadratic, and • double hashing. The required files for this lab are Driver.java, DoubleHash.java, KeyValuePair.java, LinearProbe.java, PrimeNumber.java, QuadraticProbe.java, and country-capitals.xls. You are required to submit a short report comparing, using plots, the performance of the hashing schemes for adding and retrieving items for different load factors (try at least 0.25, 0.5, 0.65). /**...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT