Question

What is the tilde time complexity for the following code fragments:

1)

int sum = 0;
for (i = n; i > 0; i /= 2)
for (j = 0; j < i; j++)
sum++;

2)

int sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j+=2)
sum++;

Answer 1

1)
Number of times each line run at max is
int sum = 0;                -> 1
for (i = n; i > 0; i /= 2)  -> log(n)
for (j = 0; j < i; j++)     -> (i+1)log(n)
sum++;                      -> ilog(n)

Max value for i is n
Time complexity
= Theta(1 + log(n)(i+1+i))
= Theta(1 + log(n)(n+1+n))
= Theta(1 + log(n)(2n+1))
= Theta(nlog(n))

=================================

2)
int sum = 0;                    -> 1
for (int i = 0; i < n; i++)     -> n+1
for (int j = 0; j < i; j+=2)    -> (1+(i/2))(n+1)
sum++;                          -> (i/2)(n+1)

Max value for i is n
Time complexity
= Theta(1 + n+1 + (1+(i/2))(n+1) + (i/2)(n+1))
= Theta(1 + n+1 + (1+(n/2))(n+1) + (n/2)(n+1))
= Theta(n^2)