1. Time and Space Complexity in C
Full Course on Data Structures and Algorithms in C
The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.
In programming, iterating means repeating some part of the code to obtain different results. This involves looping.
A loop is a compound statement whose body can be executed again and again. The body of the loop has a number of statements. A loop needs an initial state or initial statement, from which the loop will execute the first time, before repeating. Repeating, means all the statements in the body of the loop are re-executed, in order, again and again. In order for the loop to repeat after the first pass or any pass of the body, there has to be a statement that will cause it to repeat. In order for a loop to stop repeating, there has to be a condition that will cause the loop not to repeat./p>
This tutorial presents basic programming constructs that allow iterations to be performed in C (in a loop). The names of the different loops are: the do-while loop, the while-loop and the for-loop.
Do-while Loop Syntax
The syntax for the do-while loop construct is:
//initial statement here (initialization)
do {
//statements
//cause for next iteration (continue Statement)
} while (condition);
This construct should be read as follows: Considering the initial statement, do all the statements in the loop, while the condition allows it. The initial statement ends with a semicolon. The do-compound statement itself, also ends with a semicolon. Note that “while” here, is a reserved word.
There are three main loops in C: the do-while loop, the while-loop and the for-loop. This tutorial (lesson ) explains the do-while loop, the while-loop and the for-loop.
do-while Loop Example
Using the above syntax, an example of a do-while loop coding, is in the following program:
#include <stdio.h>
int main(int argc, char **argv) {
int myInt = 0;
do {
printf("%d ", myInt);
myInt++;
} while (myInt < 5);
printf("\n");
return 0;
}
The output is:
0 1 2 3 4
The complete construct begins with “int myInt = 0;” and ends at “while (myInt < 5);”. There are two simple statements in the braces. The first statement in the braces, prints out the value of the integer, myInt. The second statement increments myInt, by adding 1 to it. The condition is “while (myInt < 5)”. So, while myInt is less than 5, the compound statement is re-executed.
This loop has just one main simple statement, which is to print the value of myInt. The second simple statement is to cause the next iteration. The curly brackets can have more than one main simple statement. The following do-while loop has two main simple statements. The first one adds 2 to myInt, and the second one prints the result of the addition:
#include <stdio.h>
int main(int argc, char **argv) {
int myInt = 0;
do {
myInt = myInt + 2;
printf("%d ", myInt);
myInt++;
} while (myInt < 13);
printf("\n");
return 0;
}
The output is:
2 5 8 11 14
This output needs explanation. First of all, note that the while condition has been changed to "while (myInt < 13)".
When myInt is 0, 2 is added to it, and myInt becomes 2. Two is printed. The increment adds 1 to myInt and it becomes 3, at the beginning of the next pass. In the next iteration (pass) myInt is 3. Two is added to it again and it becomes 5. The increment adds 1 to myInt and it becomes 6. In the next iteration myInt is 6. Two is added to it again and it becomes 8. The increment adds 1 to myInt and it becomes 9. In the next iteration myInt is 9. 2 is added to it again and it becomes 11. The increment adds 1 to myInt and it becomes 12. In the next iteration myInt is 12. 2 is added to it again and it becomes 14. The increment adds 1 to myint and it becomes 15.
After each iteration, the while condition is checked. At this point, that the while condition is checked, the myInt is 15, above 13, after 14 has been printed. The condition results in false, and the repetition of the block, stops.
while-loop
The syntax for the while-loop is:
//initial statement here (initialization)
while (condition) {
//statements
//cause for next iteration (continue Statement)
}
The main difference between the do-while loop and the while-loop is, that for the while-loop, the condition is checked first, before the block is executed. With the do-while loop, the block is executed first, before the condition is checked. Note that the while-loop construct, does not end with a semicolon.
The following program repeats the first program above, but with a while-loop:
#include <stdio.h>
int main(int argc, char **argv) {
int myInt = 0;
while (myInt < 5) {
printf("%d ", myInt);
myInt++;
}
printf("\n");
return 0;
}
The output is the same as for the first program above, that is:
0 1 2 3 4
The following program repeats the second program above, but with a while-loop:
#include <stdio.h>
int main(int argc, char **argv) {
int myInt = 0;
while (myInt < 13) {
myInt = myInt + 2;
printf("%d ", myInt);
myInt++;
}
printf("\n");
return 0;
}
The output is the same as for the second program above, that is:
2 5 8 11 14
for-loop
The syntax for the for-loop is:
#include <stdio.h>
int main(int argc, char **argv) {
for (int myInt = 0; myInt < 5; myInt++) {
printf("%d ", myInt);
}
printf("\n");
return 0;
}
The block of the for-loop does not end with a semicolon. The output is the same as for the first program above, that is:
0 1 2 3 4
There is no semicolon after the increment statement (last statement) in the parentheses.
The following program repeats the second program above, but with a for-loop:
#include <stdio.h>
int main(int argc, char **argv) {
for (int myInt = 0; myInt < 13; myInt++) {
myInt = myInt + 2;
printf("%d ", myInt);
}
printf("\n");
return 0;
}
The output is the same as for the second program above, that is:
2 5 8 11 14
Conclusion
The do-while loop in C, repeats the execution of its block, as long as a condition is true. The do-while loop needs an initial statement (state), before the block. The do-while loop needs a cause-for-next-iteration (increment) statement, usually towards, the end of its block. The main difference between the do-while loop and the while-loop, is that, with the do-while loop, the block is always executed before the condition is checked; while with the while-loop, the condition is always checked before the block is executed. Both the do-while loop and the while-loop do essentially the same thing. The for-loop is a concise construct for the do-while loop or while-loop.
