Algorithms Answers

Find out the step count for the following function using tabular method.

void ABC( int n ){    

     for( int i=1;  i<= n; i++){

         for (int j=1; j<=2^n;j=j*2)  { 

                     printf(“%d”,j);

            }

    }

}

void Example2 (int n){

int a = 0;

for (int i = 0; i < N; i++) {

    for (int j = N; j > i; j--) {

               a = a + i + j;

        } 

      } 

 }

Prove weather following statements are true or false.

1. 7n3+n2 ≠ Ω(n4)
2. 9n + 3 = O(n2)
3. n*lgn + 8n2 = Ω(n3)
4. 2n + n3 + 1 = Ө(n3)

Represent the following function in form of big-oh(O) and omega(Ω) and theta(Ө)  notation. Find the required constants for it.

1. 2n2 + 25nlogn
2. 3 n3 + 4n + 11
3. 5 n3 +  n2 + 3n + 2
4. 2*2n + 6 n2 + 3n
5. 3*n3 – 4n
6. 4n4 + n + n2logn
7. ½ n2 +3n

4n2+7n+3n 3.5

Arrange the following growth functions in increasing order of growth:

       O(n1.5), O(2n), O (nlogn), O(logn), O(n3),  O() ,O(),O()

Prove that max( f(n), g(n) ) = Ө ( f(n) + g(n) )

Write algorithm to find maximum element from array and find its best and worst case time complexity.

Write bubble sort algorithm and analysis it for best case and worst case time complexity using tabular method. Represent the time complexity using Theta(Ө) notation.

Getting the age of participant, if the age is less than or equal to 17 you need to print "sorry

you're not able to join the event", else you need to print "welcome to the event.

Suppose N is a decimal number, where N represents the last 4 digits of your student

id.

i) Convert N to binary.

ii) Convert N to hexadecimal

What is space complexity? Discuss various factors affecting it. Write iterative and recursive algorithm of finding factorial of a given number and find its space complexity.