Considering the cost of only assignment and comparison operations, determine a T

Question

Considering the cost of only assignment and comparison operations, determine a T(n) for the number of operations that will be performed by the following block of code. Assume n represents the size of some input data set (an independent variable in your analysis). In some way, show your work as to how your T(n) was derived.

            int x = 0;

            for(int i = 0; i < n; i++) {

              int p = 5;

              while (p < 10) {

             x++;

                p++;

              }

            }

Explanation / Answer

The time complexity can be etermined by clculating the number of times the program execute.

The outer for loop execute n times.

In the inner while loop, the loop runs 5 times for values of p = 5 , 6 , 7 , 8 , 9

So,the total no of times the program runs is

5 * n

5n

So,

Time Complexity = O(5n)

Now, when we calculate the time complexity, we assume that n is very very large. SO, we ignore the lower order terms and the constants.

So,

Time Complexity = O(n)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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