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

..#title, whate is meant by the term heuristic

whate is meant by the term heuristic

Explain class p problems, Explain class P problems Class  P  is  a  cla...

Explain class P problems Class  P  is  a  class  of  decision  problems  that  can  be  solved  in  polynomial time  by(deterministic) algorithms. This class of problems is kno

Mcs-021, #questWrite an algorithm for multiplication of two sparse matrices...

#questWrite an algorithm for multiplication of two sparse matrices using Linked Lists.ion..

Analyze an algorithm, In order to analyze an algorithm is to find out the a...

In order to analyze an algorithm is to find out the amount of resources (like time & storage) that are utilized to execute. Mostly algorithms are designed to work along with inputs

Sparse matrix, How sparse matrix stored in the memory of a computer?

How sparse matrix stored in the memory of a computer?

Acyclic graphs, Acyclic Graphs In a directed graph a path is said to fo...

Acyclic Graphs In a directed graph a path is said to form a cycle is there exists a path (A,B,C,.....P) such that A = P. A graph is called acyclic graph if there is no cycle in

What is a height balanced tree, What is a height balanced tree? Height Ba...

What is a height balanced tree? Height Balanced Tree (AVL Tree) An AVL tree is a binary search tree in which the height of the left and right subtree of the root vary by at most

Applications in file systems of avl trees, 1. In computer science, a classi...

1. In computer science, a classic problem is how to dynamically store information so as to let for quick look up. This searching problem arises frequently in dictionaries, symbol t

Search on a hashed file, Write a program to simulate searching over a hashe...

Write a program to simulate searching over a hashed file, with different assumptions for the sizeof file pages.Write a program to perform equality search operations on the hashed f

Limitation of binary search, Limitation of Binary Search: - (i)  The co...

Limitation of Binary Search: - (i)  The complexity of Binary search is O (log2 n). The complexity is similar irrespective of the position of the element, even if it is not pres

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