Long story short this is the topic that most of the developers skip but it is the most important before you start data structures. This can reduce your time beforehand you try to appear for any coding judge problem or hackathons.
What is time complexity?
Time complexity is the times a statement is executed. Technically speaking growth of time with respect to the input during program execution.
For example,
For(i=0;i<n;i++) -> This statement will be executed n times. correct? so the Big O notation is n. O(n)! So now you know the basic concept of time complexity.
Now there are some ground rules since many of you might think that time required to execute a statement might vary from machine to machine which got cleared in the initial definition. So we take a model machine with the following specifications:
- Single processor
- 32 bit
- Sequential execution
- 1 unit of time for arithmetic and logical operations
- 1 unit of time for return and assignment statements
For example,
add(a,b){
return a+b; 2 units of time -> 1 unit of time for return statement and 1 unit of time for arithmetic operation
}
so total time = 2 = constant = O(1)
for any constant units of time, the time complexity is always 0(1) irrespective of the size of the constant.
list_items(A,n){
count=0; 1 unit of time
for(i=0 to n-1) 2 unit of time -> logical & assignment
count=count+A[i] 2 units of time -> assignment & arithmetic
return count; 1 unit of time
}
Total sum = 1+ 2*(n+1)+2*n+1
=4*n+4
cancel constant 4 and also the constant with n so the time complexity will be O(n).
so you may have a doubt regarding n+1 so basically, it will run till n+1 because it will come as a false statement.
Big O notation is basically the worst-case complexity which means the maximum time to execute a statement.
Example :
arr=[1,5,8,9]
Suppose you want to find a number in thios array i.e. 0
key=0
for(int i=0;i<arr.length;i++){
if(arr[i]==key){
return i;
}
return -1;
}
The time complexity is 0(n).
I guess most of the concept should be clear from this piece now you can solve time complexity question wherever you can find and also not forget just to be thorough go through the tutorials attached as well.
Thank you for your time! 😊
resources : geeksforgeeks,interviewbit,youtube.
