Question about wording of an algorithm-complexity problem

[s3a]

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. Homework Statement
"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)."

Homework 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)).

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!

 

[stevendaryl]

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!

Well, the assignment is to come up with an algorithm that has complexity O(n). It might also be the case that the algorithm you come up with is \Omega(n) and \Theta(n) (probably so). The situation where it's nice to consider both O-complexity and \Omega-complexity is when there are cases where the O complexity greatly over-estimates the complexity. In that case, it's nice to have a lower bound, as well. \Theta is really only used when the \Omega and O complexities are the same (which might be the case for your problem).