How to calculate the time complexity (Big "O") of the programs meant to obtain the initial coefficients of a binomial expansion in MQL4 language
How to calculate the time complexity (Big "O") of the programs meant to obtain the initial coefficients of a binomial expansion in MQL4 language
Loading saved threads...
Peter · External communityPost link
External question — Stack Overflow Stack Exchange
Author: Peter
Original post: https://stackoverflow.com/questions/72875887
License: CC BY-SA 4.0 — https://creativecommons.org/licenses/by-sa/4.0/
Adaptation: HTML converted to plain text; contact email addresses removed.
The following three blocks of codes are meant to find the initial coefficients of the expansion of a binomial expression up to power 6. That is, since (x + y)^6 = x^6 + 6x^5y + 15x^4y^2 + 20x^3y^3 + 15x^2y^4 + 6xy^5 + y^6, the program is meant to obtain the numbers 1, 6, 15, 20, 15, 6, 1 given only the input 6. Each block of code represents one of three different methods of finding the numbers. The question is: What are the Time complexity (Big "O") of each block of codes given that the input is 6 in each method? Thank you as I anticipate your answers.
First method - THE USE OF PASCAL'S TRIANGLE
void OnInit()
{
int P0, P1, P2, P3, P4, P5, P6, P7, P8,P9, P10, P11, P12, P13, P14;
int I1, I2, I3, I4, I5, I6, I7, I8,I9, I10, I11, I12, I13;
for (int row = 0; row <= 6; row++)
{
for (int col = 1; col <= 13; col++)
{
if (row == 0)
{
I7 = 1;
}
else
{
I1 = P0 + P2;
I2 = P1 + P3;
I3 = P2 + P4;
I4 = P3 + P5;
I5 = P4 + P6;
I6 = P5 + P7;
I7 = P6 + P8;
I8 = P7 + P9;
I9 = P8 + P10;
I10 = P9 + P11;
I11 = P10 + P12;
I12 = P11 + P13;
I13 = P12 + P14;
}
}
P1 = I1; P2 = I2; P3 = I3; P4 = I4; P5 = I5; P6 = I6; P7 = I7; P8 = I8; P9 = I9; P10 = I10; P11 = I11; P12 = I12; P13 = I13;
}
if(I1 != 0) Print(I1);
if(I2 != 0) Print(I2);
if(I3 != 0) Print(I3);
if(I4 != 0) Print(I4);
if(I5 != 0) Print(I5);
if(I6 != 0) Print(I6);
if(I7 != 0) Print(I7);
if(I8 != 0) Print(I8);
if(I9 != 0) Print(I9);
if(I10 != 0) Print(I10);
if(I11 != 0) Print(I11);
if(I12 != 0) Print(I12);
if(I13 != 0) Print(I13);
}
Second method - THE USE OF FACTORIAL
void OnInit()
{
int I1, I2, I3, I4, I5, I6, I7;
I1 = (6 * 5 * 4 * 3 * 2 * 1) / ((1) * (6 * 5 * 4 * 3 * 2 * 1));
I2 = (6 * 5 * 4 * 3 * 2 * 1) / ((1) * (5 * 4 * 3 * 2 * 1));
I3 = (6 * 5 * 4 * 3 * 2 * 1) / ((2 * 1) * (4 * 3 * 2 * 1));
I4 = (6 * 5 * 4 * 3 * 2 * 1) / ((3 * 2 * 1) * (3 * 2 * 1));
I5 = (6 * 5 * 4 * 3 * 2 * 1) / ((4 * 3 * 2 * 1) * (2 * 1));
I6 = (6 * 5 * 4 * 3 * 2 * 1) / ((5 * 4 * 3 * 2 * 1) * (1));
I7 = (6 * 5 * 4 * 3 * 2 * 1) / ((6 * 5 * 4 * 3 * 2 * 1) * (1));
Print(I1);
Print(I2);
Print(I3);
Print(I4);
Print(I5);
Print(I6);
Print(I7);
}
Third method: THE TABULAR METHOD
void OnInit()
{
int I1, I2, I3, I4, I5, I6, I7;
I1 = 1;
I2 = (6 * I1) / 1;
I3 = (5 * I2) / 2;
I4 = (4 * I3) / 3;
I5 = (3 * I4) / 4;
I6 = (2 * I5) / 5;
I7 = (1 * I6) / 6;
Print(I1);
Print(I2);
Print(I3);
Print(I4);
Print(I5);
Print(I6);
Print(I7);
}
Quote
Report
Post Reply
Checking account access…