Detailed! Cos2611 Summary

Detailed
COS2611
Summary

,Big-O-Notation and space and
time complexity
Space complexity is how much memory(space) is required by the algorithm if
processed by the computer
Time complexity refers to the time taken by the algorithm to complete(to solve
the algorithm)
Aim of algorithm analysis is to assess the efficiency of an algorithm.
Efficiency - How much memory algorithm occupies
 How much time it takes for algorithm to complete
An algorithm is said to be optimal if it is - processed faster
- utilises fewer memory resources
Compared to others.

Execution time of algorithms
 It is dependent on the computer used, programming language &
programmer’s style. When we analyse algorithms, we should
employ mathematical techniques that analyse algorithms
independent of specific - implementations
- computers
- or data

,To analyse algorithms we 1st count the number of basic operations in a
particular solution. Then we express the efficiency of algorithms using growth
functions.




An basic operation
 Is operation that takes 1 time unit to execute. One time unit is
theoretical time taken by a basic operation to complete.
 Examples:
o Assignment operation (e.g. today = “Monday”)
o Arithmetic operation (e.g. salary =
hoursWorked*hourlyRate)
o Comparison operation (e.g. age=20)
 A single operation: count = count + 1; This takes on
unit of time to complete.
Example: A simple If statement: Operation Cost
if(n<0) compare 1
absval =-n; assignment 1
else
absval = n; assignment 1
Total Cost = 1+1 = 2 (because only 1 of the assignment statements will be
executed in the if statement, i.e. only one branch)
Example: A simple loop Cost
i=1; 1
sum=0; 1
while(i<=n){ n+1
i=i+1; n
sum=sum+1; n
}

,n+1 because when loop is on the last iteration it checks the condition again so
the comparison operation will gets executed another time and then it exits the
loop.
Total cost = 3n+3



Running times in general:
 Loops: Running time is the running time of the statements inside that
loop times number of iterations
 Nested loops: Running time of a nested loop(inner loop) is the addition
of the running time of the statements inside this loop. Take this and
times it by the product of the iteration of the nested loop and the
iteration of the outer loop.
e.g.
Outer(4 iterations){
Nested(3 iterations){
Statement;
Statement;
}
}
Total cost= nested loop’s statements running time * ( iteration of
nested loop*iteration of outer loop)
= 2 * (3 * 4)
= 24
 If/Else: Running time is that of the test instruction(the comparison
operation) plus the larger running time of one of the branches.

Order-of-Magnitude Analysis and Big-O Notation
- We measure an algorithm’s time requirement as a function of
its problem size.
- Problem size depends on the application, e.g. Problem size for
an algorithm that calculates 𝑛𝑡ℎ prime numbers, will be
determined by the value n.

, - Say we have algorithm A and it’s problem size is n then we can
say that Algorithm A requires 5*𝑛2 time units to solve a
problem of size n.
- The most important thing to learn is how quickly an algorithm’s
time grows as a function of the problem size.
- Algorithm A requires a running time that is proportional to 𝑛2
- An Algorithms proportional time requirement is known as
growth rate.
- We compare two algorithms by comparing their growth rates.

 If algorithm A requires time proportional to f(n), Algorithm A is
said to be order f(n), and it is denoted as O(f(n)).
 The function f(n) is called the algorithm’s growth-rate function.
 Since the capital O is used in the notation, this notation is
known as the Big-O notation.
 If Algorithm A requires time proportional to 𝑛2 , it is O(𝑛2 )


Video on Big-O:
Big-O notation and Time complexity shows you how your functions grows as
your input grows.
We ask the question how much time does it take to run a function? This question
is hard to answer because it is dependent on computer, language, etc.

e.g.function:
def find_sum(given_array):
total = 0
for each I in given_array:
total +=I;
return total;

Note: The more elements in the array the more time it will take to run the
function.

,A better question to ask is: How does the runtime of this function grow as the
size of the input grows.
To answer this question we use Big O notation and Time Complexity(tools we
use to answer this question)
When we run the find_sum function he tested different array sizes and plotted
it on the graph




On y axis is the time it takes and x axis is number of elements in the array.

This pattern is called linear time complexity.
Thus time complexity is a way of showing how the runtime of a function(or
particular code) increases as the size of the input increases.
Types of time complexity:
Time complexity: linear time
Constant time(time doesn’t increase, horizontal line)
Quadratic time
Now a more mathematical way of expressing these time complexities are Big
O Notation:
-linear time can be expressed as O(n) ,n is the size of the input. In this case
the number of elements in the array. Read as “big O of n”
-Constant time can be expressed as O(1)

,-Quadratic time can be expressed as O(𝑛2 )
In our example and looking at the straight line graph we can write the
function as:
T = an+b (n is size of input, a and b are two constants)
How to find Big-o function from the given function:
Steps:
1. Find the fastest growing term
2. Take out it’s coefficient
3. Then put that into the brackets after the O
Example: T = an+b
Fastest growing term is an, take out a. Thus O(n)=an+b
Example: T=a𝑛2 +dn+e
Fastest growing term is a𝑛2 , take out a. Thus O(𝑛2 )= 𝑎𝑛2 +dn+e
Another example:
given_arr = [1,4,3, … , 10]
function:
def stupid_func(given_arr):
total=0
return total
Running the function and then getting the average running time yields this
graph:

,Express this function as T=c=0.115
Expressing this in Big-O notation: Follow the same two steps:
Fastest term is 0.115(there is only 1 term)
0.115 can be written as 0.115 x 1, thus take away 0.115. Thus we left with 1.

Thus T = c = 0.115 = O(1) This is constant time


Let’s say you wrote 2 functions to solve a problem. 1 function is constant
time and the other is linear. E.g.




O(1) O(n)
Note: Doesn’t matter how big constant is. When the input gets very large
the linear function will take more time than the constant function


Calculating time complexity without running a program and
getting average time.
Example:
given_arr = [1,4,3, … , 10]
function:
def stupid_func(given_arr):
total=0 -> O(1) //this is assignment operation(it doesn’t depend on
size of input). Thus this line takes the same amount of time, every time. Thus takes
constant amount of time

return total -> O(1) //This also takes constant amount of time

, We consider each line of code. We can add the Big-O expressions to
calculate the total time to run entire function.
T is total time to run the function. Thus T=O(1) + O(1)
= 𝑐1 + 𝑐2 (remember O(1) is a
constant value)
= 𝑐3 (adding 2 constants give you
a constant)
= 𝑐3 x 1 (rewriting it so we can
apply the steps)
= O(1)
In general: O(1)+O(1) = O(1)

Example:
given_arr = [1,4,3, … , 10]
function:
def stupid_func(given_arr):
total=0 -> O(1)
for each i in given_array: -> O(1) //we are going to leave this out of
our function T2.
total +=i -> O(1) //takes O(1) for each time it executes


return total
We are going to each line and see how much time each line takes

Thus our function: 𝑇2 = O(1) + n x O(1) + O(1) n is number of elements in
array 𝑇2 = 𝑐4 + n x 𝑐5 Remember O(1) is constant and adding
constant plus constant is a constant
= O(n)
Example:
given_2D= [ [1,4,3], Note: There are 𝑛2 number of elements in this array
[3,1,9],

, [0,5,2]]
function:




def find_sum_2d(given_2D):
total = 0 -> O(1)
for each row in array_2d:
for each i in row:
total +=i -> O(1) //constant amount of time each time,
but have to multiply it by number of elements

return total -> O(1)
Thus our function: 𝑇3 = O(1) + 𝑛2 x O(1) + O(1) n is number of elements in
array 𝑇3 = 𝑐6 + 𝑛2 x 𝑐7 Remember O(1) is constant and adding
constant plus constant is a constant
= O(𝑛2 ) Quadratic Time complexity
Example:
function:
def find_sum_2d(given_2D):
total = 0 -> O(1)
for each row in array_2d:
for each i in row:
total +=i -> O(1) //constant amount of time each time,
but have to multiply it by number of elements

for each row in array_2d:
for each i in row:
total +=I -> O(1)