Q1. Little-Oh

Recall the definition of Big-Oh:

∃c ∈ R⁺, ∃n₀ ∈ R⁺, ∀n ∈ N, n ≥ n₀ ⇒ g(n) ≤ cf(n)

Here is one variation of this definition.

Definition 1 (little-oh). Let f, g : N → R^≥0. We say that g is little-oh of f, and write g ∈ o(f), when:

∀c ∈ R⁺, ∃n₀ ∈ R⁺, ∀n ∈ N, n ≥ n₀ ⇒ g(n) ≤ cf(n)

This is a stronger property than Big-Oh, in the sense that if g ∈ o(f), then g ∈ O(f). While g ∈ O(f) says (colloquially) that "it is possible to scale up f so that it eventually dominates g," g ∈ o(f) says that "no matter how you scale f (up or down), it will always eventually dominate g." Or, in terms of rates of growth, g ∈ O(f) means that g grows at most as quickly as f, while g ∈ o(f) means that g grows strictly slower than f.

Prove the following statements about little-oh, using only the definitions of little-oh and Big-Oh. You may not use any external properties of Big-Oh in this question.

(a) Prove that for all positive real numbers a and b, if a < b then n^a ∈ o(n^b).

(b) Prove that for all functions f, g : N → R⁺, if g ∈ o(f) then f ∉ O(g).

Note: we've restricted the range of f and g to exclude 0.

Q2. A tricky nested loop

Our goal for this question is to analyse the running time of the following function:

1 def nested(n):

2 """Assume n is an integer that is greater than 1."""

3 b = 1

4 while b <= n:   # Loop 1

5 i = 1

6 while i < b:       # Loop 2

7 print(i)

8 i = i * 3

9 b = b + 1

(a) First, prove that for all functions f, g : N → R⁺ and b ∈ R⁺, if all three of the following conditions are true:

(i) g(n) ∈ O(f(n))

(ii) f(n) and g(n) are eventually ≥ b [Correction: this used to say ≥ 1]

(iii) b > 1

then log_b(g(n)) ∈ O(log_bf(n)).

You may not use any external properties about Big-Oh; we're looking for you to prove this statement using the definition of Big-Oh.

(b) Find an exact expression for the total number of iterations of the inner loop of nested, in terms of the function's input n. Your expression may contain summation notation (e.g., _i=1∑ⁿi); you do not need to simplify it here. Make sure to use the floor and/or ceiling functions to ensure that you're counting with natural numbers.

(c) Determine, with proof, a good upper bound (Big-Oh only) on the running time of nested, in terms of the value of its input n. Note that by \good" we mean that it should be possible to prove the matching Omega lower bound, even though we are not requiring it here.

You can use the statement you proved in part (a), and your solution to part (b), and the following external facts:

∀x ∈ R, x ≤ ⌈x⌉ < x + 1                                                    (Fact 1)

n! ∈ Θ (e^{n ln n - n + ½ ln n})                                               (Fact 2)

the exponent of e in Fact 2 is eventually ≥ 1                        (Fact 3)

Q3. Algorithm analysis

Consider the following function, which takes in a list of integers.

1 def my_sum(L):

2 x = 0

3 y = 1

4 n = len(L)

5 i = 0

6 while x + y < n:

7 if L[i] % 2 == 0:

8 y = y + 1

9 else:

10 x = x + y

11 i = i + 1

Let WC(n) and BC(n) represent the worst-case and best-case runtime functions of my sum, respectively.

(a) Prove that WC(n) ∈ O(n), where n is the length of the input list to my sum.

(b) Prove that WC(n) ∈ Ω(n), where n is the length of the input list to my sum.

(c) Prove that BC(n)  ∉ Θ(n), where n is the length of the input list to my sum. You can use the definition of Theta that says g ∈ Θ (f) if and only if g ∈ O(f) Λ g ∈ Ω(f).

Attachment:- Assignment Files.rar