Example of for loop:
/* The purpose of the following program is to calculate
   1 + 8 + 27 + 64 + 125 + .... n^3
   (Sum of cube of each integer from 1 to n)*/

#include<iostream.h>
int Sum(int a);

void main()
{
 int total, num;

 cout<<"We are going to calculate \n"
     <<"the sum of the cube of integer from 1 to \n"
     <<"the number that you indicate for it. \n"
     <<"Enter a number now. \n";
 cin>>num;
 total = Sum(num);
 cout<<"The sum of 1^3 + 2^3 +....+ "<<num<<"^3= "<<total<<endl;
}

int Sum(int n)
{
 int PartialSum = 0;    //Declaration count for no time.  Initialization count for one unit.
 for(int i=1; i <= n; i++)    //Count one to initialize i, n+1 for all tests, n for all the increments
    PartialSum = PartialSum + i*i*i;   //Count 4 units, =,+,*,*.
 return PartialSum;                   //Count 1 unit
}

/* Total Time: 1+(1+n+1+n)+4n+1=6n+4=O(n) */
/* You may use the formula 13+23+33+43+53+.....+n3=[n(n+1)/2]2  to calculate the total. */

Exercise:  Do the problem similar to above:  Find the sum of squares of the numbers.
               12+22+32+42+52+...+n2 = n(n+1)(2n+1) / 6

 
n 6n+4 7n
1 10 7
2 16 14
3 22 21
4 28 28
5 34 35
6 40 42
7 46 49
8 52 56
9 58 63
10 64 70
11 70 77
12 76 84
13 82 91
14 88 98
15 94 105
16 100 112
17 106 119
18 112 126
19 118 133
20 124 140

There exists 7 such that 0 < 6n+4 < 7n whenever n > 4.

So, 6n+4 = O(n)


Example of Nested Loops:
for(i=0; i<n; i++)     // count 1+(n+1)+n = 2n + 2
    for(j=0; j<n; j++) // count n*(2n+2)
        k++;           // count 1 unit each and repeated n*n times
/* Total time: (2n+2) + n*(2n+2) + n*n = 3n2+4n+2 = O(n2)  */

Example of Consecutive Statements:
for(i=0; i<n; i++)
    A[i] = 0;           //The first loop takes O(n)
for(i=0; i<n; i++)      //The second loop is a nested loop.
    for(j=0; j<n; j++)        //It takes O(n2)
        A[i]+=A[j] + i + j;
/* Total time: O(n) + O(n2) = O(n2)    */

Example of if/else Statement:
if(condition)
   S1
else
   S2
Total time = time for checking condition + the maximum time of (S1, S2).
long factorial(int n)
{
    if(n <= 1)           //Test part time = 1
       return 1;         // T(1) = 2
    else                 //more time on else part
       return n * factorial(n-1);  //"return" takes 1 step, "*" takes 1 step
}
/* T(n) = 1 + 2 + T(n-1) = T(n-1)+ 3
                         = T(n-2)+ 3 + 3
                         = T(n-3)+ 3 + 3 + 3
                         ...
                         = T(n-(n-1)) + (n-1)*3
                         = T(1) + (n-1)*3
                         = 2 + 3n-3
                         =O(n)            */

void print(int x)
{
    if (x < 4)
      cout<<x;
    else
     {
       print(x/4);
       cout<<x%4;
      }
    cout<<endl;
}
/* T(n)=1+T(n/4)+2 = O(log n) */

long fib(int n)
{
    if(n <= 1)
      return 1;
    else
      return fib(n-1) + fib(n-2);
}
/* T(n) = T(n-1) + T(n-2) + 2 and T(0) = T(1) = 2
   By Mathematical Induction, (3/2)n < T(n) < (5/3)n
   Note: check the above with Fibonacci Numbers
   It grows exponentially.                      */