Question

In Java code provide the desired Big O notation methods and then call those methods in the main.

Problem: Let n be the length of an integer array a, for each of the following classes

?(log(log(log(?))))

?([log(?)] 3 )

?(? 5 )

?(4 ? )

?(?!)

?(? ? )

write a method that takes as sole input an array a of length n, non-recursive, whose running time belongs to only one of the above classes.

Answer 1

The complexity of loops is equal to the number of time the innermost loop is executed. So O(n n) is basically equal to

A simple program for it:

import java.util.Scanner;
public class E
{
public static void main(String[] args)
{
Scanner s = new Scanner(System.in);
System.out.print("Enter no. of elements you want in array:(row n col)");
int row = s.nextInt();
int col = s.nextInt();
       int a[][] = new int[row][col];
System.out.println("Enter all the elements:");
for(int i = 0; i < row; i++)
{
           for(int j = 0; j<col;j++)
           {
               a[i][j] = s.nextInt();
           }
}
for(int i = 0; i < row; i++)
{
           for(int j = 0; j<col;j++)
           {
               System.out.print(a[i][j]+"\t");
           }
           System.out.println("\n");
}
}
}

To check the time complexity :

the no of times loop of row(I) will be executed= n(equal to no row rows)

no of times loop for col will be executed= n*n(equal for no of rows * no of cols)

so overall time complexity will be the one of the inner loop which is n*n = O(n*n)=