educative.io

Pls pls help me the time complexity of two methods, thanks a lotttt

Courses
,
#1

Hi, l am unsure about the time complexity of two methods. Could you help me to explain which case is O(m(m+n)), under which case is O(mn), and which case is O(n^2)?

Thank u soooo much!

#2

Hi @yan1,

This is Fatimah Abdullah from Educative.

Let me first explain in which case the time complexity would be O(n^2). An easy way to understand this is that it usually takes place due to a nested loop. For example:

for (int i=0; i < n; i++){
    for(int j = 0; j < n; j++){
    ...
    }
}

The statements inside the nested loop will run O(n x n) times, i.e, O(n).

Similarly, the O(n x m) will also occur because of a nested loop, but now one loop will traverse till n and the other one will traverse till m. For example:

for (int i=0; i < n; i++){
    for(int j = 0; j < m; j++){
    ...
    }
}

For the last type, I am unsure if you meant to say O(m + n). But I will explain that. So, previously you saw that we multiply in case of nested loops. However, we add in case of independent loops that exist in the same problem. So, for O(m + n), we need two independent loops where one of the loops will traverse till n and the other one will traverse till m. For example:

for (int i=0; i < n; i++){
...
}

for(int j = 0; j < m; j++){
...
}

I hope this answers your question. If you have any more doubts please review the lesson: Common Complexity Scenarios. You can also feel free to ping me again.

Fatimah Abdullah | Developer Advocate
Educative Inc.

#3

Thank you for telling me the foundations of time complexity. My question is arise from time-complexity of two codes below. Although l know typical code case, but l still fail to understand it, really hope you can help me understand it. It said in code 1 Time complexity is O(m+n) (https://www.educative.io/courses/data-structures-coding-interviews-python#time-complexity)

method1
method12204×1246 280 KB

The time complexity for this algorithm is O(n+m) where n and m are the lengths of the lists. This is because both lists are iterated over atleast once. I am try to understand it, but fail to know why it is O(m+n).
In code 2,
method2
method21550×1022 181 KB
it said that Time Complexity is O(m(m+n)) #

Since both lists are traversed in this solution as well, the time complexity is O(m(n+m))where n and m are the lengths of the lists. Both lists are not traversed separately so we cannot say that complexity is (m+n). The shorter of the two lengths is traversed in the while loop. Also, the insert function gets called when the if-condition is true. In the worst-case, the second list has all the elements that are smaller than the elements of the first list. In this case, the complexity will be O(mn). Note that if m > n, we have O(mn), otherwise the complexity is O(n2).

l don’t understand why in code2’s time complexity is O(m(m+n)), also how it can become to O(mn) and O(n2)?

Thank u so much for kindly help me. Looking forward to your replies.

yan

#4

Shouldn’t insert in Python list make it even worse because of O(n) of the operation?

According to this:
https://wiki.python.org/moin/TimeComplexity