for(int bound=1;bound<=n;bound*=2)
{
for(int i=0;i<bound;i++)
{
for(j=0;j<n;j+=2) ====> O(n/2)
{
sum+=j;
}
for(int j=1;j<n;j*=2)===> O(logn)
{
sum*=j;
}
}
}
O($\frac{n}{2}$) + O(log2n) = O(n) + O(log2n) = O(n)
for(int bound=1;bound<=n;bound*=2)
{
for(int i=0;i<bound;i++)
{
O(n)
}
}
let n= 2k, then
bound = 1 ===> i runs one time i.e., i=0
bound = 21 ===> i runs 21 times i.e., i=0,i=1
bound = 22 ===> i runs 22 times i.e., i=0,i=1,i=2,i=3
......
bound = 2k ===> i runs 2k times i.e., i=0,i=1,i=2,....i=(n-1)
===> total times = 20 + 21 + 22 + ...... + 2k = 2(k+1) - 1 = 2.2k - 1 = 2 n - 1. ===> O(n)
But each time it runs O(n) times
∴ Total Time Complexity = O(n) . O(n) = O(n2)