Analysis And Design Of Algorithms Flashcards
What is the ‘Time Complexity’?
Comparing how much time is needed to solve a particular problem of an algorithm
How do you compare the efficiency of algorithms in terms of execution time?
You quantify the number of basic operations or steps that the algorithm will need, in terms of items to be processed
How can the magnitude, or time complexity, of an algorithm be expressed?
As a function of its size
How is a linear function generally expressed?
f(x) = ax + c
How is a polynomial function generally expressed?
f(x) - ax^m + bx + c
In a polynomial function what is the value that will have the major effect?
ax^m
How is an exponential function generally expressed?
f(x) = ab^x
How is a logarithmic function generally expressed?
f(x) = a log-n x
Rank each function from quickest to slowest interim of time to complete an algorithm?
Logarithmic, linear, polynomial, exponential
What is the permutation of a set of objects?
The number of ways of arranging the objects
What is Big-O notation used to express?
The time complexity of, or performance, of an algorithm
What does O(1) describe an algorithm?
That an algorithm take constant time to execute regardless of the size of the input data set
What does O(n) describe an algorithm?
That an algorithm whose performance will grow in linear time, in direct proportion to the size of the data set
What does O(1) describe an algorithm?
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
What will a program with two nested loops each performed n times will have a time complexity of?
O(n^2)
What does O(2^n) describe an algorithm?
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
What does O(log n) describe an algorithm?
That an algorithm time taken to executive an algorithm will grow very slowly as the size of the data set increases
How do you calculate the time complexity of the algorithm in Big-O notation?
You need to count the number of basic operations it performs
