Jun 10, 2020

TIME COMPLEXITY ANALYSIS | Time Complexity Calculation | Coding winds | We care about the future of future

   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. 



No comments:

Post a Comment