Does the time complexity of code depend on loops or number of operations?

Admin 1
Viewed 648

I was making a code in which I needed to compare elements of my array with another array.

But I was thinking that this would increase my time complexity from O(n) to O(n^2) as it was already inside one for loop, for the first array.

So I came up with a code like this, inside the parent for loop (with parameter i):

int m = 0;
int ele = array2[m];
if(array1[i] == ele)
    count++;
m++;

But since the thing that is being done is same, only I have emitted a for loop, I was wondering that the time complexity indeed was O(n) or became O(n^2).

I also understand that this would only compare the same indexed elements and not all. I would appreciate if someone can part more information about this.

time-complexity algorithm java
3 Answers

Yes Time complexity depends on Loop and number of operations done within it.

In your case there is one assignment int ele = array2[m] and one conditional checking if(array1[i] == ele) along with 2 increments of m and count.

All the operations will take constant time and will depend on the number of time the loop is executing.

user_49641360

The time complexity of an algorithm depends on the way you write your loops and also the time complexity of the operation you do in the algorithm.

If your algorithm consists of any number of O(1) operations, your algorithm is O(1).

If your algorithm consists of one or more loops (not nested) from a constant to n, the time complexity is O(n * the_time_complexity_of_the_operation_in_the_loop)

Every statement below takes O(1) time:

int m = 0;
int ele = array2[m];
if(array1[i] == ele)
    count++;
m++;

so the whole thing is O(1). This block is inside a for loop that loops through your array, so the time complexity is O(n * 1) = O(n), where n is the array's length.

Here's an intuitive way to think about why the time complexity became less complex when you compare only the elements at the same index.

If you want to compare every possible pair of the two arrays, how many pairs are there? The first element of first array can form a pair with n other elements from the second array, The second element of the first array can form a pair with n elements from the second array, and so on. In general, for each element in the first array, n pairs can be formed. Assuming the two arrays are of the same length, the total number of pairs is n^2. Therefore, that many comparisons needs to be made, which means the time complexity is O(n^2).

If you want to compare the pairs elements at the same index, how many pairs can you have? n pairs, because each index correspond to exactly 1 pair. Therefore you need to make n comparisons, which means the time complexity is O(n).

user_51335850

In this case, you are always comparing the array[m] (in your case array[0]) element with i^th index of array1 array. So this is actually same as traversing one array and count the number of elements matching given specific number

Comparing one array to another usually takes O(n^2) time, though there are ways to do in lesser time complexity. Once such solution could be of O(n+m) time complexity and O(min(n,m)) space complexity. Where you Traverse the lesser sized array and store the elements in one hash table, then you traverse the second array to match the elements from hash table.

user_32114630
Related