Calculates partial sum of an integer, Data Structure & Algorithms

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).

Posted Date: 4/4/2013 5:56:50 AM | Location : United States

Related Discussions:- Calculates partial sum of an integer, Assignment Help, Ask Question on Calculates partial sum of an integer, Get Answer, Expert's Help, Calculates partial sum of an integer Discussions

Write discussion on Calculates partial sum of an integer
Your posts are moderated
Related Questions
As we talked in class, a program with two integer variables is universal. Now, we consider a special form of four variableprograms. Let G = (V; E) be a directed graph, where V is a

In the present scenario of global warming, the computer hard ware and software are also contributing for the increase in the temperature in the environment and contributing for the

Explain in brief about the Container An entity which holds finitely many other entities. Just as containers such as boxes, baskets, bags, pails, cans, drawers, and so for

A common person's faith is that a computer can do anything. It is far from truth. In realism computer can carry out only definite predefined instructions. The formal illustration o

Read the scenario (Pickerings Properties). (a) List the functions of the system, as perceived by an external user. (b) List the external entities. Note that because we are mo

B-trees are special m-ary balanced trees utilized in databases since their structure allows records to be added, deleted & retrieved with guaranteed worst case performance. A B-

A set s is conveniently shown in a computer store by its characteristic function C(s). This is an array of logical numbers whose ith element has the meaning "i is present in s". As

Explain the representations of graph. The different ways of representing a graph is: Adjacency list representation : This representation of graph having of an array Adj of

Assume a complete binary tree T with n nodes where each node has an item (value). Label the nodes of the complete binary tree T from top to bottom & from left to right 0, 1, ..., n

Q. Explain the Hash Tables, Hash function and Hashing Techniques properly?             A n s . H as h Table is explained as follows : A hash table is a data struc