1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Algorithm Analysis - Growth of Functions

  1. Mar 22, 2017 #1
    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 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...
  2. jcsd
  3. Mar 22, 2017 #2
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted