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!

Question about wording of an algorithm-complexity problem

  1. Sep 13, 2017 #1

    s3a

    User Avatar

    Hello to everyone who's reading this.

    Here is the problem whose wording I'd like to focus and elaborate on (instead of actually solving the problem, which I've been told I have already done so, successfully), where the first of the two parts is underlined, and the second of the two parts is italicized.:

    1. The problem statement, all variables and given/known data

    "Compute 1/0! + 1/1! + . . . + 1/n!, for the non-negative integer n, with the additional requirement that the number of steps (i.e., the number of assignments performed during the execution) should be of order n (i.e., not greater than Cn for some constant C)."

    2. Relevant equations
    I:
    1/0! + 1/1! + . . . + 1/n!, for a non-negative integer n

    II:
    Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. We say that f(x) is O(g(x)), if there are positive constants C and k, such that |f(x)| <= C |g(x)|, whenever x > k.

    III:
    Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. We say that f(x) is Ω(x), if there are positive constants C and k, such that |f(x)| >= C |g(x)|, whenever x > k.

    IV:
    Let f and g be functions from set of integers or the set of real numbers to the set of real numbers. We say that f(x) is Θ(g(x)) if f(x) is O(g(x)) and f(x) is Ω(g(x)).

    3. The attempt at a solution
    I believe "not greater than" is equivalent to "less than or equal to." So, the "i.e., not greater than Cn, for some constant C" part should be equivalent to saying "less than or equal to Cn, for some constant C" and therefore "O(n)," right?

    While that doesn't seem incorrect to me, it seems to be an incomplete truth, and I just wanted to make sure that I am right about it being an incomplete truth. Basically, is it the case that the algorithm sought is Θ(n) (in addition to being O(n) and Ω(n), by definition of the big theta notation)? By the way, should definition IV be an "if and only if"? That is, should IV read "Let f and g be functions from set of integers or the set of real numbers to the set of real numbers. We say that f(x) is Θ(g(x)) if and only if f(x) is O(g(x)) and f(x) is Ω(g(x))."? I get that, in practice, one would find that a function is

    I get that the big O notation is focused on, since the worst-case complexity of an algorithm is, generally, what's most important, but I just wanted to see if what I'm thinking is correct or not, so any input would be GREATLY appreciated!
     
  2. jcsd
  3. Sep 16, 2017 #2

    stevendaryl

    User Avatar
    Staff Emeritus
    Science Advisor

    Well, the assignment is to come up with an algorithm that has complexity [itex]O(n)[/itex]. It might also be the case that the algorithm you come up with is [itex]\Omega(n)[/itex] and [itex]\Theta(n)[/itex] (probably so). The situation where it's nice to consider both [itex]O[/itex]-complexity and [itex]\Omega[/itex]-complexity is when there are cases where the [itex]O[/itex] complexity greatly over-estimates the complexity. In that case, it's nice to have a lower bound, as well. [itex]\Theta[/itex] is really only used when the [itex]\Omega[/itex] and [itex]O[/itex] complexities are the same (which might be the case for your problem).
     
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: Question about wording of an algorithm-complexity problem
  1. Hashing problem (Replies: 3)

Loading...