Question

Please explain why x = x + 1 is Theta(nlgn)

code:

i = n;

while (i > 1)
{

i = floor(i/2);

x = x + 1;
}

why is is theta(nlgn)?

Answer 1

Θ notation :

It is a best case complexity so it find exact time consuming .

From the question:

i = n; // It assign only once so its complexity is Θ (1)

while (i > 1) // Number of times the loop iterate is purely depend on the i value.
{

i = floor(i/2); // let n=13 then i values are 13,6,3,1(Since we use floor) and the value are exponentially decreased so its complexity is Θ (logn) so while loop complexity is Θ (logn)

x = x + 1; // Its complexity is logn.
}

Therefore the overall complexity is Θ(logn)

Note:

Small wrong in the question the complexity is Θ(logn).

Any doubts leave a comment