1) Analyze the running time complexity (in terms of big O notation) of the follo

Question

1) Analyze the running time complexity (in terms of big O notation) of the following code segment:

for (i=0; i<a.length-1; i++)
{
for (j=i+1; j<a.length; j++)
{
if(a[i] > a[j])
{
/* switch a[i] and a[j] */
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}

****************************************************************************************

2)Write a method splitStack that takes a stack of integers as a parameter and
splits it into negatives and non-negatives. The numbers in the stack should be
rearranged so that all the negatives appear on the bottom of the stack and all
the non-negatives appear on the top. In other words, if after this method is
called you were to pop numbers off the stack, you would first get all the
nonnegative numbers and then get all the negative numbers. It does not
matter what order the numbers appear in as long as all the negatives appear
lower in the stack than all the non-negatives. You may use a single queue as
auxiliary storage. For example, if the stack stores [3, -5, 1, 2, -4] , an acceptable
result would be [-5, -4 , 3, 1, 2]

**********************************************************************************************************

3) Recursion & Big O Write a method called printStar(int n) which will print the following when n=4:

****

***

**

*

*

**

***

****

What is the Big O for this function?

Explanation / Answer

Hi, I have answered Q1 and Q3.

Please repost Q2 in separate post.

1) Analyze the running time complexity (in terms of big O notation) of the following code segment:
for (i=0; i<a.length-1; i++)
{
for (j=i+1; j<a.length; j++)
{
if(a[i] > a[j])
{
/* switch a[i] and a[j] */
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}

We have two for loops. They are nested.
Outer 'for' loop runs for (n-1) times: i=0 to i=n-1
for each value of i, inner 'for' loop runs (n-i) times:

T(n) = (n-1) + (n-2)+ (n-2) + ... + 2 + 1

   = (n-1)*n/2
   = Big-O = O(n^2)

3) Recursion & Big O Write a method called printStar(int n) which will print the following when n=4:
****
***
**
*
*
**
***
****
What is the Big O for this function?

   public static void printStar(int n){
      

       for(int i=n; i>=1; i--){ // this for loop runs n times
           for(int j=1; j<=i; j++){// for each value of i, its runs i times
               System.out.print("*");
           }
           System.out.println();
       }
       // Big-O for above loops : O(n^2)
      

       // time complexity for this loops: O(n^2)
       for(int i=1; i<=n; i++){
           for(int j=1; j<=i; j++){
               System.out.print("*");
       }
       System.out.println();
       }
   }

   Over all time complexity: O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.