CODEWITHSUNDEEP
runtimecomplexity-theorydiscrete-mathematics
C.chair
C.chair

Reputation: 1

Calculating Runtime

I'm stuck on the following problem I was able to solve the first part, however, I'm not sure how to proceed from there:

how many times does the following program print out "Hi"? That is, what is the running time? (in terms of Big-O notation)

int i = 1;
int j = 1;
while(i <= n )
{
    j+= j;
   int k = 1;
   while (k <= j)
    {
       System.out.println("Hi");
       k = k +1;
    }
    i = i + 1;
}

I was able to deduce that the program would produce Summation from x = 1 to n (2^x) amount of Hi's. Is this also the run time or should I break the code down into two summations where one is from i = 1to n and the other is ....(I don't know). Thank you for your help!

Upvotes: 0

Views: 27

Answers (2)

templatetypedef
templatetypedef

Reputation: 372972

Your runtime as a summation looks correct. So then the question is how you simplify it. Fortunately, we have this fact:

20 + 21 + 22 + ... + 2n-1 = 2n - 1.

Ignoring any off-by-one errors in substituting this sum for your sum, which we can do thanks to big-O notation, we see that “Hello!” gets printed out Θ(2n) times.

Upvotes: 1

An Nguyen
An Nguyen

Reputation: 321

Then you can try like this 

    int i = 1;
    int j = 1;
    long startTime = System.nanoTime();
    while(i <= n )
    {
        j+= j;
       int k = 1;
       while (k <= j)
        {
           System.out.println("Hi");
           k = k +1;
        }
        i = i + 1;
    }
    long endTime = System.nanoTime();
    System.out.println("time taken in nano seconds" + endTime-startTime);

Upvotes: 0

Related Questions