Algorithmic Complexity
Efficient programs are correct and computationally efficient.
Programmers often increase the conceptual complexity of a program in an effort to reduce its
computational complexity.
How do we compare two different algorithms?
Let us look at the worst-case running time of an iterative implementation of the factorial
function.
def fact(n):
"""Assumes n is a natural number Returns n!"""
answer = 1
while n > 1:
answer *= n
n -= 1
return answer
The number of steps required to run this program is something like 2 (1 for the initial assignment
statement and one for the return) + 5n (counting 1 step for the test in the while, 2 steps for the
first assignment statement in the while loop and 2 steps for the second assignment statement in
the loop). So, for example, if n is 1000, the function will execute roughly 5002 steps.
2+5n
-----------------------
What is the efficiency of the algorithm when run on very large inputs?
def f(x):
"""Assume x is an int > 0"""
ans = 0
#Loop that takes constant time
for i in range(1000):
ans += 1
print ('Number of additions so far', ans)
#Loop that takes time x
for i in range(x):
ans += 1
print ('Number of additions so far', ans)
#Nested loops take time x**2
for i in range(x):
for j in range(x):
ans += 1
ans += 1
print ('Number of additions so far', ans)
return ans
When you call the function as follows: f(10)
The output is as follows:
Number of additions so far 1000
Number of additions so far 1010
Number of additions so far 1210
The running time of this function can be described as 1000 + x + 2x 2. The constant 1000
corresponds to the number of times the first loop is executed. The term x corresponds to the
number of times the second loop is executed. Finally, the term 2x 2 corresponds to the time spent
executing the two statements in the nested for loop.
What if we run for x is 1,000 and if we run for x is 1,000,000.
---------------------------
The following rules of thumb is used in describing the complexity of an algorithm:
If the running time is the sum of multiple terms, keep the one with the largest growth rate,
and drop the others.
If the remaining term is a product, drop any constants.
“Big O” notation is most commonly used notation. Big O notation is used to give an upper bound
on the order of growth of a function. For example, the formula f(x) O(x 2) means that the function
f grows no faster than the quadratic polynomial x2
-------------------------------
Some of the most common instances of Big O are listed below where n is a measure of the size
of the inputs to the function.
O(1) denotes constant running time. Constant complexity means that it is independent of the
inputs.
O(log n) denotes logarithmic running time.
O(n) denotes linear running time.
O(n log n) denotes log-linear running time. Did you come across an algorithm that has O(n log
n)?
O(nk) denotes polynomial running time. Notice that k is a constant. When k=2, it is quadratic
complexity which means that complexity grows as the square of the size of the input.
O(cn) denotes exponential running time. Here a constant is being raised to a power based on the
size of the input. Strategy, we have to find algorithms that provide approximate solutions to the
exponentially hard problems or that find perfect solutions on some instances of the problem.
------------------------------
#What is the complexity of the following function?
def intToStr(i):
"""Assumes i is a nonnegative int
Returns a decimal string representation of i"""
digits = '0123456789'
if i == 0:
return '0'
result = ''
while i > 0:
result = digits[i%10] + result
i = i//10 #integer division
return result
str=intToStr(845)
str
#There is only one loop. We want to calculate the number of iterations.
#how many times one can divide i by 10?
---------------------------
#What is the complexity of the following function?
def addDigits(s):
"""Assumes s is a str each character of which is a decimal digit.
Returns an int that is the sum of the digits in s"""
val = 0
for c in s:
val += int(c)
return val
value=addDigits('1234')
value
Comparisons of Complexity Classes
Note that the following plot uses a logarithmic scale on the y-axis.