c++ - i want to calculate the T(n) for the two algorithms

Question

i want to know the time complexity for the following two algorithms

void main (){-----------------------------------------T(n)
for(int a=1 ; a<=20 ; a++) {------------?
if(a%2==0)  -------------?
    cout<<"value is Even"; --------?
   else 
     cout<<"value is Odd";--------?
}

}

void main (){-----------------------------------------T(n)
int x=1; {------------?
int a=1;  -------------?
   while(a<=n){--------?
   x=x*a; -------------?
   a=a+2; -------------? 

}
cout<<x;
}

Answer 1

The idea is to calculate how the execution time for a piece of code - typically some algorithm, depends on the input. If a function takes N as input how long will it take to execute if N=5 or N=10. Will it take double as long? Will it take the same time? Or will it take more than double?

In your case:

The first program doesn't depend on any input so it is O(n)=1.

Your second program depends on n. It will do the same stuff n/2 times due to the a = a + 2. So it is O(n)=n/2. However constants are typically skipped and one would write O(n) = n.

If you had code like this:

for (a=0; a < n; a++)
{
     // n times here
     for (b=0; b<n; b++)
     {
        // n times here

        // do something
     }
 }

the execution time will change to n^2 because both loops will iterate n times. Each time the outer loop executes, the inner loop executes n times. Since the outer loop executes n times, you have n*n. So O(n) = n^2