Big OH

Big "OH"

Before we proceed we must know what the below graph means

If you are wondering what it means let me be very straight forward to you.

"You have to write your algorithm with time and space complexity near or below the purple line"

When someone asks you to calculate Big-O, you do the below things and you are golden :

1. Worst Case Scenario

Always consider the worst case scenario. As yourself this, question a million times."What if the input is huge, like a million or a trillion ?"
If you have to check no of times a string occurs in an array, you would go for a for loop which will loop through the elements and keep increment a counter, which has a complexity of O(N) where N is the number of inputs. Always think, what will happen when N reaches a million or a trillion. How will your code perform.

2. Remove Constants -

I have added the Big-O complexity to the code. Final complexity is 2*O(1) + 2*O(N)

If we consider the 1st rule, and ask the question, for a data input more than a million, the constants seems very small. For Example : lets say N = 1000000000

Now 2*O(1) is negligible 2*O(1000000000) and multiplying it with 2 is also not required as the number is too big. Hence in a world with such big number the other constant associated with can be removed.

Hence the Big-O is O(N)

3. Different Terms for inputs

Its simple, the complexity depends on the number of inputs you have to work on.

So if you have two inputs A and B then Big-O for a Linear Time would be O(A+B)

4. Nested Is Always Multiply

If you see a nested loop, multiply the Inputs. These kind of Complexity is called Quadratic Time Complexity or O(N^2). If there are two inputs then O(A*B)

*More to come*

Comments

I wonder Why ?

I wonder Why ? #1 W e have "string" and "String" in C# when both does the same thing ? Answer : Answer is fairly simple. string is an alias of String. Hows that ?. To achieve type safety, Microsoft has designed the Managed languages such that they can communicate with each other. For the entire framework we have base types such as System.String and thus their code specific alias such as string in C# and String in VB. When we compile the program in C# it actually refers to System.String(Kinda how alias is suppose to work right) There are plenty of other alias too object : System. Object string : System. String bool : System. Boolean byte : System. Byte ...

Abstract Classes

ABSTRACT CLASSES : "You are so abstract ;-)" 1. Multiple Abstract classes cannot be inherited in an abstract. ( :-/ ) If you have an abstract class and you want multiple abstract classes to be inherited then it is not possible. 2. When inheriting the abstract class, you must follow the convension of inheriting the abstract class first before the interface, other wise it will show an error. COMPILER ERROR - Base class 'YourAbstractClassName' must come before any interfaces 3. An abstract class can inherit multiple interfaces. Duh !! 4. When creating a class library which will be widely distributed or reused—especially to clients, use an abstract class in preference to an interface; because, it simplifies versioning. 5. An abstract method cannot be static. 6. You can use sealed with the abstract methods. In other terms, An abstract class can be sealed.

Interface Theorem

INTERFACE : " It all started with you :-* " 1. Interface cannot inherit abstract class. In other words, An interface can only inherit other interfaces. 2. Interface can inherit multiple interfaces 3. If you have two interfaces, the second one has inherited the first one, if you inherit the second one to any class then all the methods from the first interface will have to be declared too. 4. An interface member functions or variables cannot be declared with Access Modifiers. 5. If you have inherited an Interface, then you must declare all its method as Public when you are declaring. If declared as "Protected", "Private", "Internal" or "Protected Internal", you will see an error. 6.

Overthinking Everything

Search This Blog