Hint: you\'ll want to make use of several properties of the log() function You m

Question

Hint: you'll want to make use of several properties of the log() function

You may work in pairs for this assignment. If you choose to work with a partner, make sure only one of you submits a solution, and you paste a copy of the Partners Template that contains the names and PIDs of both students at the beginning of the file you submit. You will submit your solution to this assignment to the Curator System (as HW03). Your solution must be either a plain text file (e.g., Notepad++) or a typed MS Word document; submissions in other formats will not be graded. Partial credit will only be given if you show relevant work. in all questions about complexity, functions are assumed to be nonnegative. the analysis of a certain algorithm leads to the following complexity function (for the average case): T (N) = 3 N log^2 (N) + 5 N^2 log (N) + log (N) +17 N + 2 Several computer science students offer their conclusions about the algorithm (quoted below). For each conclusion, state whether it is correct, or incorrect, or could be either correct or incorrect, based on the given information, and give a brief justification of your answer; feel free to cite any relevant theorems from the course notes. the algorithm, on average, is O (N^2). the algorithm, on average, is Ohm (N). the algorithm, on average, is Ohm (N^2 log N). the algorithm, on average, is Theta (N^2 log N). the algorithm, on average, is O (N^3). the algorithm, on average, is Theta (N log^2 N). in the worst case, the algorithm could be Theta (N^3). in the worst case, the algorithm could be Ohm (log N). in the worst case, the algorithm must be Ohm (N). the algorithm's best case performance is Ohm (N^2 log N). the algorithm's best case performance cannot be Ohm (N log N) the algorithm's best case performance is O (log N). Suppose that an algorithm takes 30 seconds for an input of 2^24 elements (with some particular, but unspecified speed in instructions per second). Estimate how long the same algorithm, running on the same hardware, would take if the input contained 2^30 elements, and that the algorithm's complexity function is: Theta (N) Theta (log N) Theta (N log N) Theta (N^2) Assume that the low-order terms of the complexity functions are insignificant, and state your answers in the form HH:MM:SS.S (hours, minutes, seconds, tenths of a second). Be sure to show supporting work. Use theorems from the course notes to solve the following problems. Show work to support your conclusions. Find the "simplest" function g (n) such that f (n) = 17 n^3/2 + 3n log n +1000 is Theta (g (n)) Find the "simplest" function g (n) such that f (n) = 5 n log^2 n + 8 n^2 log n is Theta (g (n)) Find the "simplest" function g (n) such that f (n) = Squareroot n + log (n + 1000) is Theta (g (n)) Using the counting rules from the course notes, find the exact-count complexity function T (n) for the following algorithm. Show details of your analysis, and simplify your answer. in simplifying, you may discard the floor notation. x= 100; y = 0; for (r = 1; r

Explanation / Answer

Suppose f : Z R and g : Z R are functions. We say f is O(g) if there exists constants C and k so that |f(n)|C|g(n)| for all n>k . In other words, f is O(g) if it is never larger than a constant times g for all large values of n. The function Cg(n) gives an upper bound on the size of f(n) for all large values of n. Usually the expression for g is less complex for the expression for f, and that’s one of the things that makes big-O notation useful. Notice that we don’t care what happens for “small” values of n. Also, usually we don’t worry too much about the absolute value signs since we usually compare functions that take positive values. To prove f is O(g) using the denition you need to nd the constants C and k. Sometimes the proof involves mathematical induction (for instance in showing that n2 is O(2n)), but often it just involves manipulation of inequalities. What I recommend doing in the latter case is starting with f(n) and writing a chain of inequalities that ends with Cg(n). Some of these inequalities will only be true when n is greater than some lower limit. The largest of these limits is the k you want There is no need to memorize the bounds on n; you can always work them if you have to. • 1log(n) ifn 10. • logn n if >0 (the bound on n depends on ). • n tn for >0 and t>1 (the bound on n depends on and t). • sn tn if 1 s t and n 1. • tn n! (the bound on n depends on t). • n! nn if n 1. Another importat fact is that the base of logarithms is not important. Any two log functions are related by multiplication by a constant. The formula is loga(n) = logb(n)loga(b) (so the constant is loga(b)). To prove this, start with aloga(n) = blogb(n) (both of these You should know how to prove this Fact. It implies that if f is O(g), then it is also Big-O of any function “bigger” than g. This is why one is typically interested in nding a “best possible” big-O expression for f (i.e., one that can not be replaced by a “smaller” function). Usually one can guess a “best possible” big-O estimate for a function by rst throwing away all constants, and second keeping only the biggest term in the expression. (You still need to prove that your guess is correct.) For example applying these guidelines to f(n) = 10·2nn2 +17n3 log(n)500 suggests that a best possible big-O form is O(2nn2). A quick way to decide if f is O(g) is to use limits. It turns out that f is O(g) if
lim n
|f(n)| |g(n)| exists and is nite. The proof that this works involves the denition of the limit of a function, which we have not studied. Most often you will be asked to prove f is O(g) using the denition, so this method will not be accepted.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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