Big O Notation Flashcards
What is time complexity?
How much time an algorithm needs to solve a particular problem.
How do we determine the efficiency of an algorithm (in terms of execution time)? / How do we determine the time complexity of an algorithm?
By quantifying the number of basic operations the algorithm needs to execute
What is the time complexity for an algorithm with a total of n+1 operations?
The time complexity = n
What can the order of magnitude/time complexity of an algorithm be expressed as?
It can be expressed as a function of its size
What does a function do?
It maps one set of values onto another set of values
How is a linear function expressed?
f(x) = ax + c
How is a polynomial function expressed?
f(x) = ax^m + bx + c
How is an exponential function expressed?
f(x) = ab^x
How is an logarithmic function expressed?
f(x) = (a)logn(x)
What is the permutation of a set of objects?
The number of ways of arranging the objects.
What is the formula for calculating the number of permutations?
n! (factorial)
What does Big O Notation express?
-It expresses the time complexity of an algorithm
What does O(1) describe?
An algorithm that takes constant time (the same amount of time) to execute regardless of the size of the input data set.
For example: suppose array a has n items:
length = len(a)
What does O(n) describe?
O(n) describes an algorithm whose performance will grow in linear time, in direct proportion to the size of the data set.
What does O(n^2) describe?
O(n^2) describes an algorithm whose performance is directly proportional to the square of the size of the dataset. It grows in polynomial time.
