Time complexity problem. What\'s the theta running time for question below? Note

Question

Time complexity problem. What's the theta running time for question below?

Note that the theta running time for sample below is:

So how do I do question above? There are 4 inner for loops within the main for loop, and amongst those 4 inner loops, I can find the largest term of n, then times the outermost loop running time (n), -> n*n = n^2, but what I concern about is the 1st inner for loop which the running time is basd on "i". What if I change the question to something like this:

for( i = 1; i < n; i *= 2){ <-- my opinion, this execute log(n) time

for( j = 0; j < i; j ++) { <-- execute <= n time

sum++;   

}

for(j = 0; j < n; j *=2){ <-- execute logn time

sum++;

}

}

amongst those inner, i know the largest execute time will be n time. Hence big O(nlogn).

But what about theta(n) in this question? How to find theta(n)? The upper bound will be nlogn, what is the lower bound?

My guess answer will be theta(n), I find out the largest term of inner for loop compare with the others, then check if the lower bounds of that inner for loop with the outermost loop, hence my strategy to solve this will be simplify aboved question to :

for( i = 1; i < n; i *= 2){ <-- my opinion, this execute log(n) time

for( j = 0; j < i; j ++) { <-- execute <= n time

sum++;   

}

}

Since the other inner loop is execute less than this inner loop, this inner loop hold the upperbound, so I just remove it the (logn inner loop) and simply to this. And check what's the lower bound for it.

I found out that this is theta(n),

hence, the answer is theta(n)? <- My answer

I feel that I'm not consistent with the answer, please correct me if my thought/step to solve is wrong.

Thank you.

Best Regards

Explanation / Answer

Firstly , I have to correct you one thing .

In the 1st slide , they have not mentioned that the running time is O(nlogn), rather it was a question , whether it is O(nlogn) or not.

Secondly, if (n) is the running time , then Big-Oh will also be (n).

(n) precisely means the tight bound , ie , O(n) = (n).

Now for your question :

for( i = 1; i < n; i *= 2){                             <-- my opinion, this execute log(n) time
         for( j = 0; j < i; j ++) {                       <-- execute <= n time
                sum++;       
         }
       for(j = 0; j < n; j *=2){                          <-- execute logn time
              sum++;
     }
}

As you said , this can be reduced to

for( i = 1; i < n; i *= 2){                             <-- my opinion, this execute log(n) time
         for( j = 0; j < i; j ++) {                       <-- execute <= n time
                sum++;       
         }
}

Now, this is same as the slide.

And hence , answer will be O(n) = (n) =>(n)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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