day 10 of 1000 days of code (BigO and some patterns)

ยท

2 min read

DSA- BigO tells the performance of algo, it takes into account of the worst possible outcome. There are two ways to calculate 1) time analysis and 2)space analysis.

In time analysis we calculate the number of operations (not time coz it may vary for different machines & even for the same machines it differs each time we run the programme ). It's a general calculation in which small factors are neglected. A few of rules in it are (not strict to follow) arithmetic calculations, primitive variable assignment, and accessing an element of array or object are constant. Regarding loops its complexity = (whatever inside it complexity)*(loop complexity).

In space analysis, we see if memory size grows with input or not. Once we are done with it can calculate O(f(n)) value for various f(n). In this, we calculate assignment to what, we ignore loop, functions etc. Except for string, assignment to all primitives = constant. Assignment to string, array, object =O(n).

O(1) =constant,O(n)=linear , O(n^2)=quad and so on

//doubt: Generally O(n) is better than O(n^2), but for value set [0,1] n^2 function is lower or better I think. I am not sure about this, will test it once I have enough knowledge of how to test it๐Ÿ˜….

Algorithms: steps of solving a problem (in simple words). I learnt few problem-solving patterns and practised a few questions based on them. The main aim is to reduce the big complexity for eg by avoiding nested loops.

  1. divide and conquer- We divide the input data into subsets and do operations on it, and based on its outcome we select the next subset. We repeat it till we get the desired result.

  2. Sliding window - make a subset array or number. We increase or decrease its value or replace it with a new one according to the condition.

  3. multiple pointers- store position(index) of elements of an array, then move them towards right, left or centre depending on conditions.

  4. frequency counter- in it we use an object to store the number of times an element appeared in an array.

Personal:- Sorry for not being regular recently, I am busy with some family-related work. I will try my best to keep posting blogs daily. I am not jealous but feel bad for myself and how far I have left behind in life. But instead of regretting I should focus on moving on as I still have left much life ahead.

ย