TIME COMPLEXITY : PART II
Smit PATEL
ICT GUNI Rank 1 Coder on GeeksForGeeks || Machine Learning Engineer || Codechef 3? || PYTHON & C++ programmer
"Inside every well-written large program is a well-written small program."
: - SMIT PATEL
Two loops
We have learned about the basic algorithms and their time complexities in the last few lessons, but there are many different algorithms and thus there can be a lot of different variations in time complexity as well.
See this algorithm:
for i = 0 to N
print(i)
for j = 0 to M
print(j)
What do you think will the time complexity be? Let’s calculate.
First loop => O(N) Second loop => O(M)
Total => O(N + M)
But Rule 2 says that we only care about the largest factor no?
We cannot ignore either of N or M because both are variable and we don’t know which one is bigger or smaller. So we have to keep both of them in the final complexity.
If we are already given that M is very large as compared to N, then we can say the complexity is O(M). But in general case, it is still O(N + M).
Task
Now can you think of what the time complexity will be for this algorithm?
for i = 0 to N
print(i)
for j = 0 to M
print(j)
for i = 0 to N
print(i)
Answer?: O(N+M)
Explanation:
The time complexity will still be O(N + M) as we can ignore the constant 2.
Nested loops with different variables
What do you think about the time complexity of this algorithm?
for i = 0 to N
for j = 0 to M
print(i)
Answer?: O(N*M)
Explanation:
Outer loop runs for N iterations, and for each iteration of the outer loop the inner loop again runs for M iterations.
Total operations => N * M * O(1) => O(N * M)
We cannot ignore any of N or M as both are variable.
Time complexity for?DSA
We will solve a lot of examples on time complexity, but let’s take a break and think about the applications of time complexity when it comes to solving DSA problems.
Remember how each problem statement on CodeChef has a Constraints section. This section talks about the constraint on the size of input given to you.
The constraints section generally look like this: 1≤N≤10?
This means that the value of N can range from 1 to 10?.
For harder problems it is not enough that your solution is correct, it also has to be efficient enough to run within the given time limit.
In general, you can assume that the current day computers can run up to 10 ^ 8 operations per second. You can calculate the worst case time complexity of your algorithm and check if the total number of operations are beyond 10 ^ 8. If the operations performed by your algorithm exceeds 10 ^ 8, you will get TLE or Time limit exceeded.
Task
What will the number of operations performed by your algorithm be, if maximum value of N can be 10 ^ 6 and time complexity of the algorithm is O(N)?
Answer?: 10?
Explanation:
Total operations => O(N) = 10^6 (approx.)
领英推荐
Time complexity for?DSA
Let’s go through some examples to understand how to use time complexity for programming problems.
Say you calculate the sum of numbers from 1 to N using the following algorithm
sum = 0
for i = 1 to N
sum += i
print(sum)
and the constraints on N are: 1≤N≤100
Will the above algorithm run within 1 second?
Answer?: YES
Explanation:
The time complexity of the given algorithm is O(N), which is N operations for any input N.
When N can be at most 100, the total operations will also be 100.
This can easily run within a second as the most computers support upto 10 ^ 8 operations or 100 million operations within a second.
Time complexity for?DSA
sum = 0
for i = 1 to N
sum += i
print(sum)
Can this same algorithm run within a second if the constraints on N are: 1≤N≤10??
Answer?: YES
Explanation:
Yes it can still run because 10 ^ 5 is still less than 10 ^ 8.
Time complexity for?DSA
Let’s look at another algorithm, which calculates the sum of all the pairs (i, j) where 1 <= i <= N and 1 <= j <= N.
sum = 0
for i = 1 to N
for j = 1 to N
sum += i
sum += j
Can this algorithm run within a second if the constraints on N are: 1≤N≤10??
Answer?: NO
Explanation :
The time complexity of the given algorithm is O(N ^ 2), which is N * N operations for any input N.
When N can be at most 10 ^ 5, the total operations will be 10 ^ 5 * 10 ^ 5 => 10 ^ 10.
10 ^ 10 is higher than 10 ^ 8 which is the number of operation a computer can run within a second. Thus this algorithm will give TLE or Time limit exceeded.
But this algorithm will easily work if N is less than 10 ^ 4.
Time complexity of standard algorithms
Hope you have got an idea on how to figure out whether your algorithm will work or give TLE based on the constraints provided.
The steps are -
Let’s now look at time complexity of some of the standard algorithms. Remembering this numbers help you quickly decide whether you can do that operation or not based on the constraints.
Loops
Time complexity of standard algorithms
In this lesson, we learned all about how to apply the knowledge of time complexity to find an efficient algorithm for solving DSA problems.
If your solution is not efficient, you can get Time limit exceeded on submitting the code. Approximately 108108 operations can happen in a modern computer in a second. Your code should ideally be within this limit to not get TLE.
Then we looked at time complexity of some of the standard algorithms.
From the next lesson, we will practice a lot of problems on time complexity to solidify our understanding.
Learn competitive coding for coding round for placement at multinational company, getting current repeatedly asked coding question with solution code https://lnkd.in/dXT49-FX
TIME COMPLEXITY : PART I = https://www.dhirubhai.net/feed/update/urn:li:linkedInArticle:7182662921250885632/
TIME COMPLEXITY : PART II = https://www.dhirubhai.net/feed/update/urn:li:activity:7182997926594416643/
TIME COMPLEXITY : PART III = https://www.dhirubhai.net/feed/update/urn:li:linkedInArticle:7183009887289827328/
TIME COMPLEXITY : PART IV = https://www.dhirubhai.net/feed/update/urn:li:linkedInArticle:7183018074994864128/