Time complexity

Question

1.  for ( i = 1 ; i <= n ; i++)

{

     for ( j= 1 ; j <= i; j++)

{

     for ( k = 1 ; k <= j ; k++)

        cout<<"a";

}

}

     

Here , complexity = O(n³)

 

2.

for ( i = 1 ; i <= n ; i=i*2)

{

     for ( j = 1 ; j <= i ; j++)

        cout<<"a";

}

Here , complexity = O(n) . But I am getting O(2^n)

 

(A gp was formed , first term = 1 = 2^0 , last term was 2^n so sum is 2^(n+1) which gives complexity as 2^n)

Comments

for  question (a)

The complexity can be written as ,

$\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{j}x$      [ x is constant amount of work]

= $\sum_{i=1}^{n}\sum_{j=1}^{i} (j*x)$

=$x\sum_{i=1}^{n}\sum_{j=1}^{i} j$

=$x\sum_{i=1}^{n}\frac{i(i+1)}{2}$

=$x\sum_{i=1}^{n}\frac{i^{2}}{2}+x\sum_{i=1}^{n}\frac{i}{2}$

=$\frac{x}{2}\sum_{i=1}^{n}i^{2}+\frac{x}{2}\sum_{i=1}^{n}i$

=$\frac{x}{2}*\frac{n(n+1)(2n+1)}{6}+\frac{x}{2}\frac{n(n+1)}{2}$

=$O(x*n^{3})$

As x is constant amount of work so time complexity is $O(n^{3})$.

 

Question 2:-

The time complexity can be written as ,

The outer loop say run for k times .

Then, $2^{k}=n$

So,$k=\log_{2}n$

Now the inner loop will run total,

$2^0+2^1+2^2+2^3+2^4+.......+2^k$

=$\frac{2^{k+1}-1}{2-1}$

=$2^{k+1}-1$

=$2.2^k-1$

=$2n-1$

=$\theta(n)$

---

What is the most effective way to deal with dependent nested loops as I am getting errors many times ?

Please tell step by step approach

Thanks in advance :)

---

Why no comparison + substitution is done in question 1 like it is done in question 2 i.e 2^k = n ?

---

@Ferox  Depending on the question you can use any approach which is convenient to you .I have used the summation method which is useful in question 1 but question 2 is rather simple one so just sum them all the term .

For question 1 there is no need to substitute anything . I have not sum the term there as the dominating power is $n^3$ which is easily seen there which will be big oh term .

 

 

---

you can also solve 2^nd one as:

$S = 1+2+4\ +...+\frac{n}{2} + n$

$S = 1+ 2(1+2+…+\frac{n}{2})$

$S = 1+2(S-n)$

$S = 2n-1$

---

Thanks ankit , I get errors while doing this and you got the correct answer. May you please tell how you started solving these ?

What are various approaches for dependent nested loops ?

Also what are sources from where I may get such practice questions ?

---

Thanks kabir , you mentioned approach that is convenient to me . This is what I am unable to know that which approach will fit as I don't know how many approaches are there.

1.how many ways are there

2. From where and How you have started for these methods , plz tell.

---

@Ferox you can start from here and then move to CLRS book (I have started from these two resources and one indian author book). And then you can solve previous year questions of all the exams which are available here and you can also solve questions from various QA sites like math.stackexchange(MSE), stackoverflow and cs.stackexchange by searching tag “time complexity” and various university questions too.

I guess you are new to this topic, so it will need some time and practice. It is expected to get error and so, you have to see solution sometimes and also, sometimes you will see different approaches and sometimes you will invent new approaches for a particular question.