TIME
COMPLEXITY ANALYSIS
Before reading this you must have knowledge about the Time Complexity Basics.
If you have already read it then you can continue.
We generally analyze
Time Complexity for two conditions –
(i)
Very
large input size
(ii)
Worst
case scenario
Some important general
rules regarding Time Complexity analysis are -
Rule 1 – Ignore lower order terms
Rule 2 – Ignore constant multiplier
For Example,
T(n) = 4n3 + 7n2 + 14n
+5
Here, at infinite value of 'n', lower order terms will become negligible as compared to 'n3', therefore we ignore lower order terms and we also ignore the constant multipliers.
Therefore, time
complexity here will be T(n) = O(n3)
Let's have a look on one more example :
T(n) = 4n + 8 log(n)
As we ignore the
lower order terms here we ignore log(n)
term therefore the time complexity here will be T(n) = O(n).
Rule 3 – Time complexity of a programme is the
summation of the time complexity of it’s fragments
Let’s look for an eample below which is divided into three fragments ;
T(n) = TFrag.1 + TFrag.2 + TFrag.3
T(n) = O(1) + O(n) + O(n2)
Here also, we will ignore the lower order terms, therefore
T(n) = O(n2)
Rule 4 – In conditional statements time complexity depends
on worst case
In this programming,
worst case is considered for the time complexity
therefore, T(n) = O(n2)
So, yes this is all
we have for you on this, hope you get the maximum out of it.
If you still have any doubt on this topic then do come to us via email "sophomoretechs@gmail.com" or via instagram "@coding.winds".
We also have an article on space complexity, give it a read by clicking here.
