ALGORITHM ANALYSIS

Question 1

is an important part of computational
complexity theory, which provides theoretical estimation for
the required resources of an algorithm to solve a specific
computational problem.

Answer 1

ALGORITHM ANALYSIS

Question 2

(1)______ of (2)______ is the determination of the amount of
time and space resources required to execute it.

Answer 2

(1)ANALYSIS (2)ALGORITHM – ALGORITHM ANALYSIS

Question 3

TYPES OF ALGORITH ANALYSIS

Answer 3

BEST CASE
WORST CASE
AVERAGE CASE

Question 4

Define the input for which algorithm takes less time or minimum time.

Answer 4

BEST CASE

Question 5

In the _______ calculate the lower bound of an algorithm.

Answer 5

BEST CASE

Question 6

In the linear search when search data is
present at the first location of large data then the _______ occurs.

Answer 6

EXAMPLE OF BEST CASE

Question 7

Define the input for which algorithm takes a long time or maximum time.

Answer 7

WORST CASE

Question 8

In the ________ calculate the upper bound of an algorithm.

Answer 8

WORST CASE

Question 9

In the linear search when search data is not present at all then the ______ occurs.

Answer 9

EXAMPLE OF WORST CASE

Question 10

In the ________ take all random inputs and calculate the computation time for all inputs. And then we divide it by the total number of inputs.

Answer 10

AVERAGE CASE

Question 11

Notations in Complexity Analysis of
Algorithms

Answer 11

BIG-O NOTATION (O)
OMEGA NOTATION (Ω)
THETA NOTATION (Θ)

Question 12

◦We define an algorithm’s worst-case time complexity by using the ________ , which determines the set of functions grows slower than or at the same rate as the expression.

Answer 12

BIG-O NOTATION

Question 13

it explains the maximum amount of time an algorithm requires to consider all input values.

Answer 13

BIG-O NOTATION

Question 14

◦It defines the best case of an algorithm’s time complexity, the ________ defines whether the set of functions will grow faster or at the same rate as the expression.

Answer 14

OMEGA NOTATION

Question 15

it explains the minimum amount of time an algorithm requires to consider all input values.

Answer 15

OMEGA NOTATION

Question 16

◦It defines the average case of an algorithm’s time complexity, the __________ defines when the set of
functions lies in both O(expression) and Omega(expression), then ________ is used.

Answer 16

THETA NOTATION

Question 17

This is how we define a time complexity average case for an algorithm.

Answer 17

THETA NOTATION

Question 18

The ____________ of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the
length of the input.

Answer 18

TIME COMPLEXITY

Question 19

How to get the time complexity? GIVE ALL

Answer 19

◦Break the algorithm/function into individual operations.
◦Calculate the big O of each operation.
◦Add up big O of each operation together
◦Remove the constants
◦Find the highest order term.

Question 20

How to get the time complexity? GIVE THE FIRST TWO STEPS

Answer 20

◦Break the algorithm/function into individual operations.
◦Calculate the big O of each operation.

Question 21

How to get the time complexity? GIVE THE LAST THREE STEPS

Answer 21

◦Add up big O of each operation together
◦Remove the constants
◦Find the highest order term.

Question 22

The amount of memory needed to solve a particular instance of the computational issue.

Answer 22

SPACE COMPLEXITY

Question 23

TWO MAIN COMPONENT OF SPACE COMPLEXITY – GIVE FIRST

Answer 23

◦A fixed part that is a space required to store certain data and variables, that are independent of the size of
the problem. For example, simple variables and constants used, program size, etc.

Question 24

TWO MAIN COMPONENT OF SPACE COMPLEXITY – GIVE SECOND

Answer 24

◦A variable part is a space required by variables, whose size depends on the size of the problem.

Question 25

◦A fixed part that is a space required to store certain data and variables, that are independent of the size of
the problem. For example, simple variables and constants used, program size, etc.
◦A variable part is a space required by variables, whose size depends on the size of the problem.

Answer 25

TWO MAIN COMPONENT OF SPACE COMPLEXITY