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

Data structures, #quCreate a flowchart to show the process that will allow ...

#quCreate a flowchart to show the process that will allow the implementation of Queue, Enqueue, and Dequeue operations.estion..

Division-remainder hashing, According to this, key value is divided by any ...

According to this, key value is divided by any fitting number, generally a prime number, and the division of remainder is utilized as the address for the record. The choice of s

Designed to manage the booking, Beauty Salon is a system to be designed to...

Beauty Salon is a system to be designed to manage the booking and the payment of a single beauty parlour. Beauty Therapists: A beauty parlour has a number of staff members mo

Recursive function, The location of a node in a binary search tree is defin...

The location of a node in a binary search tree is defined as a string such as LLRRL, which represents the node that you find by starting at the root, and traversing Left, traverse

Hash clash, Q. What do you understand by the term by hash clash? Explain in...

Q. What do you understand by the term by hash clash? Explain in detail any one method to resolve the hash collisions.

Explain what is stack. describe ways to execute stack. , ST AC K is ...

ST AC K is explained as follows : A stack is one of the most usually used data structure. A stack is also called a Last-In-First-Out (LIFO) system, is a linear list in

Algorithm of decorated graph, As we talked in class, a program with two int...

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

Example of back face detection method, Example of Back Face Detection Metho...

Example of Back Face Detection Method To illustrate the method, we shall start with the tetrahedron (pyramid) PQRS of     Figure with vertices P (1, 1, 2), Q (3, 2, 3), R (1,

Time complexity, The  total  of  time  needed  by  an algorithm to run to i...

The  total  of  time  needed  by  an algorithm to run to its completion is termed as time complexity. The asymptotic running time of an algorithm is given in terms of functions. Th

Implement an open hash table, In a chained hash table, each table entry is ...

In a chained hash table, each table entry is a pointer to a collection of elements. It can be any collection that supports insert, remove, and find, but is commonly a linked list.

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