Algorithm Analysis - Growth of Functions

[emeraldskye177]

The problem statements, all variables and given/known data:

Question 1

Question 2

Relevant equations: Provided in question snips.

The attempt at a solution:

Question 1: I think qux is the answer because it properly increments k by 1 in each iteration. j = j * 2 means j is always 0 so its loop never exits, and i = i++ doesn't actually increment i (as far as I know it should be i = ++i or just ++i or just i++) so i is always 0 and its loop never exits. But I'm not sure if this is the kind of answer they're looking for...

Question 2: I think (a) is no because, though c₁ * g > f, the actual un-vertically-translated g could be less than f? Meaning its lower bound c₂ * h < f, meaning h < f since c₂ > 0. Am I correct on this?

(b) I think the answer is yes. Am I correct in saying, if f is O(g), then g is necessarily Ω(f)? But I'm not sure how to prove it as requested in the question...

 

[emeraldskye177]

bump..