# How will I calculate the time and space complexity for this pyramid algo? [duplicate]

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?

## 1 Answer

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.

• 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? – CATALUNA84 Feb 3 '20 at 19:42
• 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) – Siddhant Aggarwal Feb 5 '20 at 14:42