0
$\begingroup$

This is an algo. programmed for displaying a letter pyramid if the buildPyramids() method is passed argument str, i.e. "12345":

    1
   121
  12321
 1234321
123454321

Code:

void buildPyramids(string str) {
    size_t len = str.length();

    size_t i, j, k, m;

    for(m=0; m<len; m++) {
        for(i=len-m-1; i > 0; i--) {
            cout << " ";
        }
        for(j=0; j<=m; j++) {
            cout << str[j];
        }
        for(k=1; k<j; k++) {
            cout << str[j-k-1];
        }
        cout << endl;
    }
}

What's the correct way to calculate the space and time complexity for the same?

Could you also guide me to some resources for a deeper understanding of the same?

$\endgroup$
1
$\begingroup$

There is one major for loop in this case

for(m=0; m<len; m++)

It has a complexity of O(len) Inside this loop, there are 4 other loops, but they are additive in nature and not nested. Each of those loops has a length of <=len. Thus the overall complexity of this program would be O(len*len) The space complexity will be also be the same.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yeah, I get that for the two levels of depth here. But, since the nested loop comprises of further three loops that are additive in nature, how should I go about calculating the exact complexity, based on the calculations taking each variable into account? $\endgroup$ – CATALUNA84 Feb 3 at 19:42
  • $\begingroup$ All you should care about it what is the largest loop in those additive iterations. The other loops are redundant. Since you know all loops will go for <=len, the complexity for those 3 loops is O(len) $\endgroup$ – Siddhant Aggarwal Feb 5 at 14:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.