educative.io

Isn't the Time complexity O(n2)?

Courses
,
#1

//Find number of odd elements in arr

for (int i = 0; i < arr.length; i++) {

  if (arr[i] % 2 != 0) oddElements++;

}

//Put odd values from arr to the resulted array

for (int i = 0; i < arr.length; i++) {

  if (arr[i] % 2 != 0) 

    result[result_index++] = arr[i];

} //end of for loop

This is two iterations of the array. Makes it O(n2) not O(n)

#2

Hi Girija!

One complete iteration over an array is O(n). Therefore, two iterations over a single array will be O(n+n), which is O(2n), not O(n^2). Ignoring the constant in O(2n) makes the final time complexity come up to be O(n).

2 Likes