Basic operations a. Define a basic operation b. Tell how to located it in a func

Question

Basic operations a. Define a basic operation b. Tell how to located it in a function c. Tell how to located it in a functions that calls another function d. Tell how to locate it in a (small) program. List the steps necessary to complete a Big-O (Ohm, theta) proof. Using the formal definitions of Big-O show that a. n^2 + n + 11 elementsof O(n^2) b. n^2 elemenmtsof O(n^2 + 6n) c. Ig(n) elementsof O(n) Using the definitions of Big-O and ohm and theta a. Show that n^2 + 3n + lg(n) elementsof O(n^2) b. Show that n^2 + 3n + lg(n) elementsof Ohm(n^2) c. show that n^2 + 3n + lg(n) elementsof theta(n^2) Using the definitions of Big-O and o a. Show that n o(n) using a proof by contradiction

Explanation / Answer

1)

a) A basic operation in any algorithm is the smallest task that is used for generating that particular algorithm. Any step like an assignment operation or comparison of two variables or the arithmetic operation applied on variables in termed as the basic operation of an algorithm.

b) In big algorithms the basic operations can be referred to as a single step in the algorithm. Hence to locate a basic oepration in a function you can use the steps to locate the basic oeprations applied on the function. For example in the step a=a+b , 2 basic operations are applied i.e; assignment and the arithmetic operation.

c) Basic operations constitutes the steps of the functions. To locate them in the functions called by the other function we have to break the functions into the steps and then we have to get the basic operations which are used for the construction of that particular step.

d) Generally in the small programs we assume basic operations to be proportional to the number of steps present in the program.

2) Steps necessary for completing the proof are:

a:- Find all the basic operations of the program.

b:- Calculate the number the times the steps are going to be executed on the basis of the input provided to the program. It will be a function in terms of n.

c:- Sum all functions that are calculated.

d:- Now apply different operation on the basis of the definition of the order you want to calculate.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

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