Suppose you have an algorithm that always takes 312 steps to complete, regardles

Question

Suppose you have an algorithm that always takes 312 steps to complete, regardless of the input size. Thus, we can write T(n) = 312.

a. Using the formal definition of Big-O, show that the function T(n) = 312 is O(1). Remember that this means you must demonstrate that there exist two constants n0 and c that meet the requirements in the formal definition.

b. Suppose you have another algorithm that always takes 10282 steps to execute, regardless of its input size. In other words, T(n) = 10282. Using the formal definition of Big-O, show that this function is still O(1).

Explanation / Answer

There is no such linear growth asymptotic O(n + k) where k is a constant. If k were a constant and you went back to the limit representation of algorithmic growth rates, you'd see that O(n + k) = O(n) because constants drop out in limits.

Your answer may be O(n + k) due to a variable k that is fundamentally independent of the other input set n. You see this commonly in compares vs moves in sorting algorithm analysis.

To try to answer your question about why we drop k in Big-O notation (which I think is taught poorly, leading to all this confusion), one definition (as I recall) of O() is as follows:

formula

Read: f(n) is in O( g(n) ) iff there exists d and n_0 where for all n > n_0,
f(n) <= d * g(n)

Let's try to apply it to our problem here where k is a constant and thus f(x) = k and g(x) = 1.

Is there a d and n_0 that exist to satisfy these requirements?
Trivially, the answer is of course yes. Choose d > k and for n > 0, the definition holds.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.