Part 4 Flashcards
What is big O notation?
A way of representing the worst case run time of an algorithm
O(n) indicates that the algorithm time
increases proportionally to the number of elements
What is the value of
k X T1(n)
where k is a positive constant
O(f(n))
the value of
T1(n) + T2(n)
is
O(max(f(n), g(n)))
the value of
T1(n) X T2(n)
is
O(f(n) X g(n))
an exponential algorithm has time complexity
O(2n)
To specify a lower bound, rather than an upper bound, Big __ notation is used
Ω
Why can very precise mathematical calculations of running time not be made?
It is impossible to know what will be generated by the compiler
Can only make guesses
T(n) is approximately proportional to f(n) if there exist some constants C and D such that
T(n) >= Cxf(n) and T(n)<=Dxf(n)
Why does the formal definition of a meaning for “approximately proportional to” ignore small values of n?
Lots of algorithms have running time approximately proportional to log2(n)
In this case, It is impossible to find a value for D which works when n is 1 because log2(1) is 0
T(n) is said to be O(f(n)) if there exist constants C and N such that
T(n) <= Cxf(n) for all values of n greater than or equal to N
It is impossible to produce a general-purpose sorting algorithm whose average-case running time is better than
O(nlog2(n))
What is the time complexity of simple expressions and assignments in Java?
O(1)
What is the time complexity of
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
sum = sum+j;
O(n2)
