Question

In: Computer Science

What is time Complexity each of the following function? 1- void function(int n) {             for (int...

What is time Complexity each of the following function?

1-

void function(int n)

{

            for (int i=n/2; i<=n; i++)  

                        for (int j=1; j<=n/2; j++)

                                    for (int k=1; k<=n; k = k * 2)

                                                print ”Hello”;

}

2-

void function(int n)

{

            for (int i=n/2; i<=n; i++)  

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

                                    for (int k=1; k<=n; k = k * 2)

                                                print ”Hello”;

}

3-

void function(int n)

{

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

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

                                                print ”Hello”;

}

4-

Int n=22^k

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

{

             J=2

            While(j<=n)

            {

                        j=j2

                        print ”Hello”;

            }

}

5=

If n>=2

While(n>1)

{

            n=n/2;

            print ”Hello”;

}

Solutions

Expert Solution

1-

void function(int n)

{

            for (int i=n/2; i<=n; i++)  

                        for (int j=1; j<=n/2; j++)

                                    for (int k=1; k<=n; k = k * 2)

                                                print ”Hello”;

}

ANSWER:n3

---------------------------------------------------------------------------------------------------------------------------

2-

void function(int n)

{

            for (int i=n/2; i<=n; i++)  

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

                                    for (int k=1; k<=n; k = k * 2)

                                                print ”Hello”;

}

ANSWER:n3

---------------------------------------------------------------------------------------------------------------------------------------------------

3-

void function(int n)

{

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

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

                                                print ”Hello”;

}

ANSWER:n2

---------------------------------------------------------------------------------------------------------------------------------------------------

4-

Int n=22^k

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

{

             J=2

            While(j<=n)

            {

                        j=j2

                        print ”Hello”;

            }

}

ANSWER:n2

---------------------------------------------------------------------------------------------------------------------------------------------------

5=

If n>=2

While(n>1)

{

            n=n/2;

            print ”Hello”;

}

ANSWER:n

---------------------------------------------------------------------------------------------------------------------------------------------------


Related Solutions

) Write a recurrence relation of the following code and find the time complexity. void towerOfHanoi(int...
) Write a recurrence relation of the following code and find the time complexity. void towerOfHanoi(int n, char from_rod,                     char to_rod, char aux_rod) {     if (n == 1)     {         cout << "Move disk 1 from " << from_rod << " to " << to_rod<<endl;         return;     }     towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);     cout << "Move disk " << n << " from " << from_rod << " to " << to_rod << endl;     towerOfHanoi(n - 1, aux_rod, to_rod, from_rod); }
Analyze the following codes by computing their running time, T(n). 1) int function ( int n)...
Analyze the following codes by computing their running time, T(n). 1) int function ( int n) { int sum; for (int i = 0; i < n; i++) ​ sum = sum + (i * n); return sum; } 2) int function(int n) { ​int sum; ​ ​for (int i = 0; i < n; i++) ​​if (n < 1000) ​​​sum++; ​​else ​​​sum += function(n); } 3) int function(n) { ​int s = 0; ​for (int i = 1; i...
Write a C function, for example void sumOfPrime(int n), that takes a positive int n as...
Write a C function, for example void sumOfPrime(int n), that takes a positive int n as a parameter, put all prime numbers less than n into an array, and print out the array and the sum of the numbers in that array. You can use the isPrime function above to save time.
In c++ Rewrite the following recursive method into an iterative function.  void mystery (int n) {  ...
In c++ Rewrite the following recursive method into an iterative function.  void mystery (int n) {    cout<<"? ";    if (n > 0)      mystery (n - 1); }
Please explain this code line by line void printperm(int *A,int n,int rem,int j) {    if(n==1)...
Please explain this code line by line void printperm(int *A,int n,int rem,int j) {    if(n==1)       {        for(int k=0;k<j;k++)        cout<<A[k]<<" + ";        cout<<rem<<"\n";        return;       }     for(int i=0;i<=rem;i++)    {          if(i<=rem)          A[j]=i;          printperm(A,n-1,rem-i,j+1);    } }
What is the ouput of the following code? void loop(int num) { for(int i = 1;...
What is the ouput of the following code? void loop(int num) { for(int i = 1; i < num; ++i) { for(int j = 0; j < 5; ++j) { cout << j; } } } int main() { loop(3); return 0; }
Find the runtime of this function, where n is an integer. int function(int n) { int...
Find the runtime of this function, where n is an integer. int function(int n) { int a = 0; for (int i = n; i > 0; i--) { for (int j = 0; j < i; j++) { a = a + i + j; } } return a; } Find the runtime of this function, where m and n are two integers. int f(int m, int n) { if (m==1 || n==1) { return 1; } return f(m,...
//2.-------------------------------------------------------------- Given an array of size N, what is the complexity? int m = A[0]; for...
//2.-------------------------------------------------------------- Given an array of size N, what is the complexity? int m = A[0]; for (int i=1; i<N; i++) { if (A[i] > m) m = A[i]; } int k = 0; for (int i=0; i<N; i++) { if (A[i] == m) k++; } What is a (name one) most frequent operation performed?______________________ Expression showing the number of times it is performed ___________ Time Complexity in Big-O Notation O( ) _____________________________________________________ //3.-------------------------------------------------------------- int mult(int N, int M) {   ...
Consider the following function: int counter( int n) { int s = 0;    for ( int...
Consider the following function: int counter( int n) { int s = 0;    for ( int i = 0; i < n; i++)             for ( int j = i; j > 0; j--)                        s = s + 1;   return s; } Part (a): How many times "s=s+1;" will be executed? Determine a precise count.  Show all your work. Part (b): What is the time complexity of the "counter" function in terms of Big-O notation? Justify and show all your work.
Consider the following C code that outlines Fibonacci function int fib (int n) { if (n...
Consider the following C code that outlines Fibonacci function int fib (int n) { if (n == 0) return 0; else if (n==1) return 1; else return fib(n-1) + fib (n-2); } For this programming assignment, write and test an ARMv8 program to find Fibonacci (n). You need to write a main function that calls the recursive fib function and passes an argument n. The function fib calls itself (recursively) twice to compute fib(n-1) and fib (n-2). The input to...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT