Help with computing time complexity Please please please sho

Help with computing time complexity. Please, please, please show your work, I need to learn how to do these, not just get the answer.

Solution

a)This is a function names sum which takes an integer \'n\' as input and returns integer named \'sum\' as output. After a function is called, it is executed from the first line and stopped when a return statement is executed or if all the statements are executed.

Let us take input n=10, the for loops executes 3 times i.e 10/2=5,5/2=2,2/2=1, the next step if statement is executed and i==1 becomes true and control comes to outer loop where sum=1 is returned.So the output of the function is 1. No matter what is the input whether it is 10,100 or 1000 the output will be 1 and the no of times the for loop is executed is less than the given number \'n\' as we have seen with the example 10.

int sum(int n)

{

int sum=n; //Since it is intialization,i.e a simple assignment statement, this step takes a constant time.Let us assume O(1).

//As explained above this for loop executes less than the given input \'n\'.To be specific, it executes log₂(n) times.

for(int i=0;i<n;i++)

{

sum=sum/2;

if(sum==1)//comparision step, it also takes constant time O(1).

{

break;//executed when sum becomes one.As break statement is used to break out of the inner loops, the program skips to the outer loop where the return statement is located.This step takes constant time O(1).

}

}

return sum; //executed only once,so takes constant time O(1)

}

Total time complexity T(n) = O(1)+O(log n)+O(1)+O(1)

Constant times can be neglected, Therefore total time complexity for the above function is O(log n).

b) This function is a special one where the total time complexity depends on the variable \"k\"

Let us assume, if the value of n is 100 and value of k is 50.Then the outer loop i.e

for(i=0;i<n;i=i+k)

{

} executes 2 times where as the inner loop i.e

for(j=0;j<i;j++)

{

//some O(1) statements

} executes 50 times since the loop is dependent on i because of the statement \"j<i\" which in turn depends on k and the output will be 50.

Now, Let us assume k=10, then outer loop executes 10 times and inner loop 450 times (10+20+30+40+50+60+70+80+90) times.

So, we can conclude that the no of times the loops will execute depends on the value of k.Specifically, if the value of k is greater, the less no of times the loops will execute and if k is lesset, then greater the loops will execute.

For generalisation, outer loop executes O(log n) and inner loop executes O(k+i) .

Total Time Complexity is O((k+i) log n).

c) This is a recursive function. A function is said to be recursive if the function calls itself. This recursion can be seen in \" int sum= sum(n-1)+1\" statement where is is calling sum decerementing value of n with 1.

Let us assume input n=5, then first statement starts running int sum= sum(n-1)+1 where n=5.

Below is the flow of function calling .

sum(5)->sum(4)->sum(3)->sum(2)->sum(1).

This function doesnt have an output because the base case in this function where n==0 returns \"sum\" which doesnt have any value as any computation didn\'t take place. The given input is 5 and the number of times the function executed is 5 times.

If given number is assumed as \'n\' then Total time complexity is O(n).

For calculating time complexities of a recursive function, you can refer to master\'s theorem which can product the answer in Big-theta notation. For general loop statements, Big-oh is preferrable.