15.What is the Big-O time complexity for an algorithm to display the n th intege

Question

15.What is the Big-O time complexity for an algorithm to display the nth integer in a linked chain of integers and why?

16.Given f(n) = …..what is g(n), the dominant term?

17.Problem size is defined as

18.To measure the time requirement of an algorithm, we must

19.For large values of n which statement is true?

20.If an algorithm requires 7 basic operations for an algorithm with a problem size of n, the algorithmic complexity is

21.What is the time complexity of the following if statement?

22.The effect of doubling the input size on an algorithm with time complexity O(n3) is

23.When you remove an item from a stack, you remove it from

24.Stacks exhibit which type of behavior?

25.Given the following infix expression, which one of the following is the corresponding postfix expression?   ….

26.Using the Postfix evaluation algorithm, evaluate the following postfix expression.

Assume that w = 3 , x = 4, y = 2, z = 7.

27.In a linked-chain implementation of a Stack ADT, when a node is popped from the stack

28.In an array-based chain implementation of a Stack ADT, the entry peek returns may be found at

29.   (4 pts) X is a queue of Integers. What are the contents of queue X through the following operations? (Be sure to clearly indicate the front of the queue.)

                _______________________________________________________

30.   (4 pts) Given a queue X of integers containing 7, 2, 5, 9, 3, 3 (from front to rear), what would be the result of each of the following statements if they are executed in that order? (Assume that k is an int.)

31.   (2 pts) When enqueueing an element on circular array implementation of a queue, the Java statement to update (wrap around) the front variable is:

Explanation / Answer

15)

1. When solving a computer science problem there will usually be more than just one solution. These solutions will often be in the form of different algorithms, and you will generally want to compare the algorithms to see which one is more efficient.

2. This is where Big O analysis helps – it gives us some basis for measuring the efficiency of an algorithm.

3. It is used to measure the efficiency of an algorithm based on the time it takes for the algorithm to run as a function of the input size. Think of the input simply as what goes into a function – whether it be an array of numbers, a linked list, etc.

4. When doing Big-O analysis, "input" can mean a lot of different things depending on the problem being solved. In our examples above, the input is the array that is passed into the different functions. But, input could also be the number of elements of a linked list, the nodes in a tree, or whatever data structure you are dealing with.

16)

1. By definition, f(n) = O(g(n) if and only if f(n) is bounded within some constant multiple of g(n) after n grows past some constant.

2. And a way to think of f(n) = o(g(n)) is that as n grows to infinity, g(n) will continue to outgrow f(n) faster. In other words:

f(n) = o(g(n)) if and only if the limit f(n)/g(n) becomes zero as n goes to infinite.

17)

1. An important aspect of performance analysis is the study of how algorithm performance varies with parameters such as problem size, processor count, and message startup cost.

2. In particular, we may evaluate the scalability of a parallel algorithm, that is, how effectively it can use an increased number of processors.

3. One approach to quantifying scalability is to determine how execution time T and efficiency E vary with increasing processor count P for a fixed problem size and machine parameters. This fixed problem analysis allows us to answer questions such as, What is the fastest I can solve problem A on computer X ? and What is the greatest number of processors I can utilize if I want to maintain an efficiency of 50 percent? The latter question may be of interest if a computer is shared and there is a charge for each processor used.

18)

1. In computer science, algorithmic efficiency are the properties of an algorithmwhich relate to the amount of computational resources used by the algorithm.

2. An algorithm must be analysed to determine its resource usage. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process.

For maximum efficiency we wish to minimize resource usage.

3. However, the various resources (e.g. time, space) cannot be compared directly, so which of two algorithms is considered to be more efficient often depends on which measure of efficiency is considered the most important, e.g. the requirement for high speed, minimum memory usage or some other measure of performance.

19)

For large values of n, we must consider the efficient method to solve the problem.

20) If an algorithm requires 7 basic operations for an algorithm with a problem size of n, the algorithmic complexity is O(n).

21) The time complexity of the if statement is depends on the statements it contains. For example the if statement is used to calculate square of a number, its time complexity is O(n^2).

23) When you remove an item from a stack, you remove it from Last. Because its operation is LIFO. Last In First Out.

24) Stacks exhibit behavior, LIFO: Last In First Out.

25) The conversion examples is shown in below.

30) Given a queue X of integers containing 7, 2, 5, 9, 3, 3 (from front to rear), what would be the result of each of the following statements if they are executed in that order 7, 2, 5, 9, 3, 3 because it Queue.

FIFO: First In First Out.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.