in Algorithms retagged by
172 views
0 votes
0 votes
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)
in Algorithms retagged by
by
172 views

4 Comments

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 ?
0
0
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.
0
0

@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.  

1
1

Please log in or register to answer this question.