Calculates partial sum of an integer, Data Structure & Algorithms

Assignment Help:

Now, consider a function that calculates partial sum of an integer n. int psum(int n)

{

int i, partial_sum;

partial_sum = 0;                                           /* Line 1 */

for (i = 1; i <= n; i++) {                                /* Line 2 */

partial_sum = partial_sum + i*i;            /* Line 3 */

}

return partial_sum;                                                 /* Line 4 */

}

This function returns the sum by i = 1 to n of i squared, which means p sum = 12 + 22+ 32

+ .............  + n2 .

Ø  As we ought to determine the running time for each of statement in this program, we ought to count the number of statements which are executed in this process. The code at line 1 & line 4 are one statement each. Actually the for loop on line 2 are 2n+2 statements:

  • i = 1; statement: simple assignment, therefore one statement.
  • i <= n; statement is executed once for each value of i from 1 to n+1 (until the condition becomes false). The statement is executed n+1 times.
  • i++ is executed once for each of execution of body of the loop. It is executed for n times.

Therefore, the sum is equal to 1+ (n+1) + n+1 = 2n+ 3 times.

In terms of big-O notation described above, this function is O (n), since if we choose c=3, then we notice that cn > 2n+3. As we have already illustrious earlier, big-O notation only provides a upper bound to the function, it is also O(nlog(n)) & O(n2), since n2 > nlog(n) > 2n+3. However, we will select the smallest function which describes the order of the function and it is O (n).

Through looking at the definition of Omega notation & Theta notation, it is also apparent that it is of Θ(n), and thus ?(n) too. Because if we select c=1, then we see that cn < 2n+3, therefore ?(n) . Since 2n+3 = O(n), & 2n+3 = ?(n), this  implies that 2n+3 = Θ(n) , too.

Again it is reiterated here that smaller order terms and constants may be avoided while describing asymptotic notation. For instance, if f(n) = 4n+6 rather than f(n) = 2n +3 in terms of big-O, ? and Θ, It does not modify the order of the function. The function f(n) = 4n+6 = O(n) (through choosing c appropriately as 5); 4n+6 = ?(n) (through choosing c = 1), and thus 4n+6 = Θ(n). The spirit of this analysis is that in these asymptotic notation, we may count a statement as one, and should not worry regarding their relative execution time that may based on several hardware and other implementation factors, as long as this is of the order of 1, that means O(1).


Related Discussions:- Calculates partial sum of an integer

Tree structure, We would like to implement a 2-4Tree containing distinct in...

We would like to implement a 2-4Tree containing distinct integer keys. This 2-4Tree is defined by the ArrayList Nodes of all the 2-4Nodes in the tree and the special 2-4Node Root w

Stack and array, how to implement multiple stack using single dimension arr...

how to implement multiple stack using single dimension array in c

Darw a flowchart to inputs top speeds of 5000 cars, Write an algorithm in t...

Write an algorithm in the form of a flowchart that: inputs top speeds (in km/hr.) of 5000 cars Outputs fastest speed and the slowest speed Outputs average (mean) s

Explain in detail about the abstract data type, Abstract data type The ...

Abstract data type The thing which makes an abstract data type abstract is that its carrier set and its operations are mathematical entities, like geometric objects or numbers;

Process of accessing data stored in a serial access memory, The process of ...

The process of accessing data stored in a serial access memory is same to manipulating data on a By using stack  method.

The various ways in which lc code can be accessed, Problem Your LC code...

Problem Your LC code is stored in a memory location as shown and the variable name is LC                  LC Memory address       Content(LC code)

Multidimensional array in one dimensional array, Q. By giving an example sh...

Q. By giving an example show how multidimensional array can be represented in one the dimensional array.

STACK, 5. Implement a stack (write pseudo-code for STACK-EMPTY, PUSH, and P...

5. Implement a stack (write pseudo-code for STACK-EMPTY, PUSH, and POP) using a singly linked list L. The operations PUSH and POP should still take O(1) time.

Just a quick couple questions, I was wanting to know where this web site wa...

I was wanting to know where this web site was created. My second question is,,, are the online tuters accredited teachers? If they are, are they only working for the website or ma

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd