Click here to Skip to main content
14,976,129 members
Please Sign up or sign in to vote.
1.80/5 (2 votes)
See more:
Time Complexity of this code ?? and how can i optimize it further?
Java
import java.util.* ;
  
class GFG
{
  
    static void AlternateRearrange(int arr[], int n) 
    { 
        // Sort the array
          
        // Collection.sort() sorts the
        // collection in ascending order
        Arrays.sort(arr) ;
          
        ArrayList v1 = new ArrayList(); // to insert even values 
        ArrayList v2 = new ArrayList(); // to insert odd values 
      
        for (int i = 0; i < n; i++) 
            if (arr[i] % 2 == 0) 
                v1.add(arr[i]); 
            else
                v2.add(arr[i]); 
      
        int index = 0, i = 0, j = 0; 
      
        boolean flag = false; 
      
        // Set flag to true if first element is even 
        if (arr[0] % 2 == 0) 
            flag = true; 
      
        // Start rearranging array 
        while (index < n) 
        { 
      
            // If first element is even 
            if (flag == true) 
            { 
                arr[index] = v1.get(i); 
                i += 1 ;
                index += 1 ;
                flag = !flag; 
            } 
      
            // Else, first element is Odd 
            else
            { 
                arr[index] = v2.get(j) ; 
                j += 1 ;
                index += 1 ;
                flag = !flag; 
            } 
        } 
      
        // Print the rearranged array 
        for (i = 0; i < n; i++) 
            System.out.print(arr[i] + " "); 
    } 
      
    // Driver code 
    public static void main(String []args) 
    { 
        int arr[] = { 9, 8, 13, 2, 19, 14 }; 
        int n = arr.length ;
      
        AlternateRearrange(arr, n); 
    } 
}


What I have tried:

This is the best approach i can think of
Posted
Updated 12-Apr-21 19:58pm
v2
Comments
CPallini 12-Apr-21 16:17pm
   
You didn't tell us what your code is supposed to do.
Samanvay Shrivastava 12-Apr-21 16:20pm
   
To Rearrange Odd and Even values in Alternate Fashion in Ascending Order from the given array.
raddevus 12-Apr-21 16:27pm
   
Time-complexity would be O(n^2) because you iterate through n items once in the foreach loop and then once in the while loop.
The print part isn't really a part of the algorithm and should actually be removed into a separate function and shouldn't really be counted as an iteration through the items, since it is just for output.
Patrice T 12-Apr-21 18:09pm
   
What is your problem with time complexity ?

1 solution

Time complexity is probably dominated by the Array.sort call, that, according to this page Time Comparison of Arrays.sort(Object[]) and Arrays.sort(int[]) | Baeldung[^] is O(n log(n)).
There are still few little improvements you can make to your code in order to make it faster (e.g. first separate odd and even numbers then sort the corresponding arrays, avoid doing additional conditional tests: once you pick the first item then you have to pick items alternatively from the two arrays, without testing each time, ...).
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900