Complexity Problems

Question 1

time complexity of an algorithm can be expressed as

Answer 1

a polynomial.

Question 2

To compare the two algorithms, we can

Answer 2

compare the respective polynomials.

Question 3

The asymptotic notation compares two functions, say

Answer 3

f(n) and g(n)

for very large values of n.

Question 4

One of the asymptotic notations is the

Answer 4

Big O notation.

Question 5

Once we have obtained the time complexity of an algorithm by counting the number of primitive operations, we can arrive at the Big O notation for the algorithm simply by:

Answer 5

Dropping the multiplicative constants with all terms
Dropping all but the highest order term

Question 6

constant coefficients have become insignificant in the Big-Oh notation

Answer 6

unless both functions have the same order

Question 7

constants represent the number of —— on a given line of code.

Answer 7

primitive operations

Question 8

What matters in the the Big-Oh notation is

Answer 8

correctly counting the number of times each line of code is repeated.

Question 9

how Big-Oh notation is done?

Answer 9

by just counting the number of executions of each line of code, instead of the number of operations.

Question 10

time complexity involves other types of functions like

Answer 10

<in>
Constant
Logarithmic
Log-square
Root-n
Linear
Linearithmic
Quadratic
Cubic
Quartic
Exponential
Exponential
n-Factorial
</in>

Question 11

in the ascending order of rate of growth Any function can be given as Big O of any other function that appears ——

Answer 11

later