Algorithm Analysis - Growth of Functions

1 reply · 2K views · last reply
emeraldskye177
Messages
26
Reaction score
0
The problem statements, all variables and given/known data:

Question 1

Pseudocode for function xyzzy(a list of n elements): an outer while loop on i, with foo(list), an inner while loop on j calling bar(list), and an innermost while loop on k calling qux(list) with k = k + 1, then j = j * 2 and i = i++.


Question 2
Homework question 4 with two parts: if f(x) is O(g(x)) and g(x) is Omega(h(x)), with quantified definitions and marks, asking whether f(x) must be O(h(x)) and whether h(x) must be O(g(x)).


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 c1 * g > f, the actual un-vertically-translated g could be less than f? Meaning its lower bound c2 * h < f, meaning h < f since c2 > 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...