Analysis And Design Of Algorithms

Question 1

What is the ‘Time Complexity’?

Answer 1

Comparing how much time is needed to solve a particular problem of an algorithm

Question 2

How do you compare the efficiency of algorithms in terms of execution time?

Answer 2

You quantify the number of basic operations or steps that the algorithm will need, in terms of items to be processed

Question 3

How can the magnitude, or time complexity, of an algorithm be expressed?

Answer 3

As a function of its size

Question 4

How is a linear function generally expressed?

Answer 4

f(x) = ax + c

Question 5

How is a polynomial function generally expressed?

Answer 5

f(x) - ax^m + bx + c

Question 6

In a polynomial function what is the value that will have the major effect?

Answer 6

ax^m

Question 7

How is an exponential function generally expressed?

Answer 7

f(x) = ab^x

Question 8

How is a logarithmic function generally expressed?

Answer 8

f(x) = a log-n x

Question 9

Rank each function from quickest to slowest interim of time to complete an algorithm?

Answer 9

Logarithmic, linear, polynomial, exponential

Question 10

What is the permutation of a set of objects?

Answer 10

The number of ways of arranging the objects

Question 11

What is Big-O notation used to express?

Answer 11

The time complexity of, or performance, of an algorithm

Question 12

What does O(1) describe an algorithm?

Answer 12

That an algorithm take constant time to execute regardless of the size of the input data set

Question 13

What does O(n) describe an algorithm?

Answer 13

That an algorithm whose performance will grow in linear time, in direct proportion to the size of the data set

Question 14

What does O(1) describe an algorithm?

Answer 14

That an algorithm whose performance is directly proportional to the square of the size of the data set, the running time grows in polynomial time

Question 15

What will a program with two nested loops each performed n times will have a time complexity of?

Answer 15

O(n^2)

Question 16

What does O(2^n) describe an algorithm?

Answer 16

That an algorithm where the time taken to execute will double with every additional item added to the data set, the execution time grows in exponential time

Question 17

What does O(log n) describe an algorithm?

Answer 17

That an algorithm time taken to executive an algorithm will grow very slowly as the size of the data set increases

Question 18

How do you calculate the time complexity of the algorithm in Big-O notation?

Answer 18

You need to count the number of basic operations it performs