4 | Elementary operations / Asymptotics II

Question 1

Elementary operation?

Answer 1

• execution time can be bounded above by a constant depending on particular implementation.
• constant does not depend on size of instance

more:
- elementary operations take a unit cost!
- we only care about running time to within multiplicative constant, only parameter that matters is number of elementary operations
- Number of elementary operation IS NOT THE SAME AS Number of lines

Question 2

Can multiplication be considered an elementary operation?

Answer 2

depends on size of numbers

Question 3

Examples of elementary operations

Answer 3

additions
subtractions
multiplications
divisions
modulo operations
Boolean operations
comparisons
assignments

Question 4

how does euclids algorithm achieve sublinear time complexity

Answer 4

This is because the size of the problem is effectively reduced by half in each recursive call, similar to the divide-and-conquer strategy seen in algorithms with logarithmic time complexity
~~~
function euclid(a, b):
if b is 0:
return a
else:
return euclid(b, a mod b)
~~~

Question 5

Best algorithm for greatest common divisor of two numbers

Answer 5

Euclid

function gcdEuclid(𝑚, 𝑛) (assuming 𝑚 is the smaller)
    while 𝑚 > 0
        𝑡 ← 𝑚
        𝑚 ← 𝑛 𝑚𝑜𝑑 𝑚
        𝑛 ← 𝑡
    return 𝑛

(vs
- use the definition - O(m)
- factorize into primes - factorization takes long time

Question 6

Complexity: ‘in the order of [O(__)] …’ meaning

Answer 6

We say that 𝒕(𝒏) is in the order of f(𝒏) [ O(f(𝒏)) ] if 𝒕(𝒏) is bounded from above by a positive real multiple of 𝒇(𝒏) for a sufficiently large 𝑛.

𝑡(𝑛) ≤ 𝑐𝑓(𝑛) whenever 𝑛 ≥ 𝑛₀

–> Every instance of a given size 𝑛 can be solved in time proportional to 𝑛 (or less)

Question 7

What is n₀

Answer 7

The value of n for which the algorithm is overtaken by its upper bound

Question 8

How to prove that f(n) is bound from above by g(n)?

What does this also mean?

Answer 8

there exists n₀ and c such that for all n > n₀, f(n) < cg(n)

f(n) is in the order of O(g(n))
O(g(n)) is the upper bound of f(n)

Question 9

Maximum rule

Answer 9

𝑂 𝑓 𝑛 + 𝑔(𝑛) = 𝑂(max(𝑓 𝑛 , 𝑔(𝑛)))

Message: Focus only on the most dominant term

Question 10

How to prove that a function t(n) is not in the order of another function f(n)

Answer 10

Use proof by contradiction!

Example.
𝑡 𝑛 = 0.001𝑛³, 𝑓 𝑛 = 1000𝑛^2</sup

(can also use limit rule)

Question 11

Limit rule:

lim 𝑓(𝑛)
𝑛→∞ 𝑔(𝑛)

is in R⁺

–> ?

Answer 11

then 𝑓(𝑛) ∈ 𝑂(𝑔 𝑛 ) and 𝑔(𝑛) ∈ 𝑂(𝑓 𝑛 )

and

𝑓(𝑛) ∈ Θ(𝑔(𝑛))

Question 12

Limit rule:

lim 𝑓(𝑛)
𝑛→∞ 𝑔(𝑛)

= 0

–> ?

Answer 12

then 𝑓(𝑛) ∈ 𝑂(𝑔 𝑛 ) and 𝑔(𝑛) ∉ 𝑂(𝑓 𝑛 )

and

𝑓(𝑛) ∈ 𝑂(𝑔(𝑛)) and 𝑓(𝑛) ∉ Θ(𝑔(𝑛))

Question 13

Limit rule:

lim 𝑓(𝑛)
𝑛→∞ 𝑔(𝑛)

= ∞

–> ?

Answer 13

then 𝑓(𝑛) ∉ 𝑂(𝑔 𝑛 ) and 𝑔(𝑛) ∈ 𝑂(𝑓 𝑛 )

and

𝑓(𝑛) ∈ Ω(𝑔(𝑛)) and 𝑓(𝑛) ∉ Θ(𝑔(𝑛))

Question 14

L’hopital’s rule

when to use?

Answer 14

lim 𝑓(𝑛)
𝑛→∞ 𝑔(𝑛)

= 0/0 or ±∞/±∞

Question 15

Upper bound formal definition?

Answer 15

𝛀(𝑓(𝑛))

„Omega of 𝑓(𝑛)„

The set of all functions 𝑡(𝑛) such that 𝑡 𝑛 ≥ c𝑓(𝑛) , 𝑛 ≥ 𝑛₀, for c a positive real.

There exists an instance of a given size 𝑛 that can be solved in time proportional to 𝑓(n)

Question 16

Duality rule?

Answer 16

𝑡(𝑛) ∈ 𝛺(𝑓 𝑛 ) if and only if f 𝑛 ∈ 𝑂(𝑡(𝑛))

Question 17

Average case complexity

Answer 17

𝛩(𝑓(𝑛)) = 𝛺(𝑓(𝑛)) ∩ 𝑂(𝑓(𝑛))

The set of all functions 𝑡(𝑛) such that 𝑑𝑓(𝑛) ≤ 𝑡(𝑛) ≤
𝑐𝑓(𝑛) , 𝑛 ≥ 𝑛₀ for 𝑐, 𝑑 positive reals.