Chapter 4

Question 1

Does the analysis of algorithm gives real time of execution

Answer 1

Yes

Question 2

What is polynomial algorithm

Answer 2

polynomial time O(n)^k means Number of operations are proportional to power k of the size of input

Question 3

What is exponential algorithm

Answer 3

exponential time O(k)^n means Number of operations are proportional to the exponent of the size of input

Question 4

What is asypmtotic growth rate of the function

Answer 4

theta (n square)

Question 5

What is summation

Answer 5

adding

Question 6

How do we analyze the running time of an algorithm that has complex nested loops

Answer 6

Write loops as summations and then solve the summations