1. Not finding help here? Sign up for a free 30min 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!

Algorithm Analysis - Growth of Functions

  1. Mar 22, 2017 #1
    The problem statements, all variables and given/known data:

    Question 1

    upload_2017-3-22_3-1-31.png

    Question 2
    upload_2017-3-22_3-2-57.png

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Algorithm Analysis - Growth of Functions
  1. Big-Oh proof (Replies: 2)

Loading...