5 | Analysis of simple structures

Question 1

What does sequencing refer to?

Answer 1

Algorithm made up of single instructions or sub-algorithms being run in a certain order

sequencing = order to run things in (change with loops, conditionals, functions etc)

Question 2

How many times will a while loop run if it is while i <= m?

for loop?

Answer 2

both m+1

Question 3

for 𝑖 ← 𝑝 to 𝑞 step s do
𝑆(i)

How many repetitions?

Answer 3

⌊(𝑞−𝑝)/𝑠⌋ + 1

(greatest integer that is smaller than (or equal to) (q-p)/s

Question 4

2 properties of recursive algos?

Answer 4

1. A simple base case (or cases). Terminating, they can be executed on their own
2. A set of rules that reduce all other cases to the base

Question 5

Fibonacci algo: recursive

Answer 5

```function FibRec(𝑛)
if 𝑛 < 2 return 𝑛
else return FibRec(𝑛 − 1) + FibRec(𝑛 − 2)
~~~

Question 6

Fibonacci algo: for loops

Answer 6

function Fibonacci(𝑛)
    𝑖 ← 1                               
    𝑗 ← 0
    for 𝑘 ←1 to 𝑛 do
        𝑗 ←𝑖 + 𝑗
        𝑖 ←𝑗 − 𝑖
    return 𝑗

Question 7

Proof for fibonacci algo for loop complexity for large numbers

eg:
```
for 𝑘 ←1 to 𝑛 do
𝑗 ←𝑖 + 𝑗 ≤ 𝑐′𝑘 (single summation)
𝑖 ←𝑗 − 𝑖 ≤ 𝑐′′𝑘 (single subtraction)
…
~~~

Answer 7

t(i) <= c*i

Σ_1<=i<=n ci

= cΣ_1<=i<=n i

= c* n(n+1)/2

is in O(n²)

Question 8

Fibonacci recursion algo

```function FibRec(𝑛)
if 𝑛 < 2 return 𝑛
else return FibRec(𝑛 − 1) + FibRec(𝑛 − 2)
~~~

Analyse complexity

Answer 8

Let 𝑇(𝑛) be the time to compute FibRec(𝑛)
Let 𝑐 be the time to exectute ‘if 𝑛 < 2 return 𝑛’
Let ℎ(𝑛) be the time to do the recursion control and addition

Then:
𝑇 𝑛 = { 𝑐, if 𝑛 < 2 return 𝑛
𝑇(𝑛 − 1) + 𝑇(𝑛 − 2) + ℎ(𝑛)

If ℎ(𝑛) is bounded by a constant.
Induction tells us that 𝑇 𝑛 ∈ 𝑂(𝑓𝑛).

Since 𝑓<sub>𝑛</sub> is exponential in the value of 𝑛, the time isdouble-exponential in the size of 𝑛.
Recall – size is the logarithm of the value

…..

fn in O(tau<sup>n</sup>) ?

tau = (1 + root(5))/2

Question 9

Binary search algorithm

Answer 9

function binarySearch(𝑇[1. . 𝑛], 𝑥)
    𝑖 ←1
    j ←𝑛
    while 𝑖 < 𝑗 do
        𝑘 ← ⌊(𝑖+𝑗)/2⌋
        case 𝑥 < 𝑇[𝑘]: 𝑗 ← 𝑘 − 1
                 𝑥 = 𝑇 [𝑘]: 𝑖 ← 𝑘; 𝑗 ← 𝑘
                 𝑥 > 𝑇[𝑘]: 𝑖 ← 𝑘 + 1
    return 𝑖

Question 10

How to analyse while loops?

Answer 10

more difficult than for: no obvious way how many times we go through the loop (it is based on a condition)

Standard technique
- find a function of the variable whose value decreases each time through the loop

Another technique
- treat the while loop as a recursion

Question 11

Analysis of binary search algorithm

function binarySearch(𝑇[1. . 𝑛], 𝑥)
    𝑖 ←1
    j ←𝑛
    while 𝑖 < 𝑗 do
        𝑘 ← ⌊(𝑖+𝑗)/2⌋
        case 𝑥 < 𝑇[𝑘]: 𝑗 ← 𝑘 − 1
                 𝑥 = 𝑇 [𝑘]: 𝑖 ← 𝑘; 𝑗 ← 𝑘
                 𝑥 > 𝑇[𝑘]: 𝑖 ← 𝑘 + 1
    return 𝑖

Answer 11

find a function of the variable whose value decreases each time through the loop.

what decreases is the number of elements to be considered:
initially 𝑑 = 𝑛, with 𝑗 = 𝑛 and 𝑖 = 1
let 𝑑 = 𝑗 − 𝑖 + 1

when does the loop terminate?
when 𝑑 ≤ 1

Three possibilities in the loop (cases):
- Let 𝑑 and 𝑑‘ be the values of 𝑗 − 𝑖 + 1 before and after the iteration under consideration
- Let 𝑖,𝑗 and 𝑖′,𝑗′ be the values before and after the iteration

Question 12

rule for counting the number of iterations in a summation?

Answer 12

= upper bound − lower bound + 1