Click here to Skip to main content
15,501,490 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?
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) 
        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 
                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
Updated 12-Apr-21 20:58pm
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     CRLF
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, ...).
Share this answer

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