Big O Notation

 Why we Need It

one problem has many solutions but which solution is best is decided by big O in mathematical terminology

Who cares

In a real-life scenario it's just your program should work you should provide an outcome to it .how it works really doesn't matter but it matters in interviews or if you have big(VERY BIG) data structure

Units To decide which one is better

More reliable units are faster and less memory though readability is very relevant but we don't measure it on the basis of it.

On The basis of time

See in snippet(code) why you should not use time

If same algo is run is super computer than it will run fast and if same algo run in old version computer it will run slow so moral of the story is you cannot depend on time

If not Time Than what

Better way is to count the number of operation computer has to perform.I have two examples

first we will look at second example how many operation it is doing (*,+,/)=>so 3 operation which will always remain same whatever the n value is

Now look at 2nd example 

Looking dangerous right but don't waste your intelligence counting each and every thing just look at the bigger picture.Most of the operations are increasing respective of its n value ex if n is 100 we have to add 100times and assign 100 times to total.So moral is operation is proportional to n.

Finally Introduction To Big O

we will not go to that dangerous theoretical definition.We will describe it according to what we understood till now.

1.It is way of formalize that fuzzy counting

2.So it tells us how the runtime of algo grows as the input grows.

Mostly there are 3 measurements

1.Linear example above in add function when we use for loop.

2.Constant example above when we use mathematical n(n+1)/2

3.quadratic example

Constant doesn't matter in big O

Always look at bigger picture

use slide to explain this

Rules Of Thumbs(Things which don't affect the operation)(just have an idea don't focus that much )

1.Arithematic operations are constant ie 1+1 or 100*100 its just one operation.

2.Variable assignment is constant a=10 is same as a=1000;

3.Accessing elements in an array (by index) or object (by key) is constant

4.In a loop, the the complexity is the length of the loop times the complexity of whatever happens inside of the loop

Note-(More example in slide)

Space Complexity

We can use Big O not only to count time but also space.There is one very high profile word called "Auxillary space complexity" which means space required  by algo and not inputs.So whenever I talk about space complexity I mean auxiliary space complexity.

Ruls Of Thumb For Space complexity

• Most primitives (booleans, numbers, undefined, null) are constant space 1 or 1000 will take same space
• Strings require O(n) space (where n is the string length) "ekta" will take 4 unit space
• Reference types are generally O( n), where n is the length (for arrays) or the number of keys (for objects) more the array length more the space

Some Example

1.

total and i are constant so whatever the value will be constant space will be allotted to them. so Big o will be O(1) space.

2.

here newArray length increases proportional to arr length so here big O will be O(n) space.

Now Lets Face The Math (Logarithem).

Till now We've encountered some of the most common complexities: O(1), O(n), O(n  )

Sometimes big O expressions involve more complex mathematical expressions

One that appears more often than you might like is the logarithm!

This is not a mathematics learning we we will make a rule of thumb.logarithem is number of times you divide the number till you get a value that is less than or equal to 1.

Mostly the base is 2 but it can be 3 ,10 etc.

Who cares

searching,sorting algo use logarithm.Recursion use logarithem .We will study deeply when we will reach there.