Before I begin, I will suggest some books which I have gone through for competitive coding and technical interviews, so if you want to read any of the chapters in detail please refer these books.

• Coding Interview Questions by Narasimha Karumanchi
• Introduction to Algorithms by CLRS
• Cracking the coding interview by Gayle Laakmann McDowell

TIME AND SPACE COMPLEXITY

First and foremost we need to understand why do we need data structures and algorithms. Well, the answer is simple to solve problems based on imaginary or real-world situations. If it were not for such data structure and algorithms, we would have to do things manually. You cannot imagine your computer functioning without Stack, queue, and job scheduling algorithms, and so on.

When I say imaginary. It's similar to Maths right. We all have seen questions like "XYZ buys 400 watermelons", does anyone ever, though? Still, we just imagine and solve it.

Let's begin with the basic topic which, while solving problems helps us in understanding whether our code will be accepted or not. It sounds important right, so don't miss it. Generally, this is something people learn along the way since you will get the picture when you get Time limit exceptions, etc.

What is time complexity?

In simple terms, Given the size of input, time complexity is the amount of time a program takes to complete its execution for that input, it is generally expressed in Big O notation. You can always read the wikipedia definition.

What is space complexity?

Space complexity is the amount of space a program takes to complete its execution given the size of the input to the program, it is also generally expressed in Big O notation.Here is the wikipedia definition.

Why do time and space complexity come into the picture?

Time and space complexity and overall optimising solutions comes into the picture because of the limitations of technology we have. A typical server can execute ~10^8 computations per second, well you might disagree but for most coding platforms you can assume this.Also, the server allows a memory of 50KB or so depending on the program. Time and memory constraints are generally mentioned in the program itself. So with limited constraints, when you have to implement your solution it becomes imperative to understand these complexities and code your solution accordingly.

What is Big O Notation?

For a given function, Big O denotes the worst space/time the resultant function will have, it is usually dependent on N, the size of the input, or O(1) for constant values. There are other notations like Omega, Theta but that is not important from competitive programming's perspective. For instance this example,

A simple evaluation of O(f(N)) for any function f(N) will be taking the highest power present in the function. Like N^2 was the highest power of N in the above example. Now, we translate our code to these functions, on the basis of time/space each statement will take. Let's see some examples, (I will be focussing on Time complexity here)

A good practise will be to go over random solutions and evaluate the time/space complexities. Now, if you want to understand these theoretically and in detail which you should do, I would suggest you to go through books/blogs. There are lots of examples you will find , so I don't want to duplicate stuff.

Complexity and Solution Effectiveness

Now coming to the part which actually matters in competitive coding, how can you determine whether your solution is effective enough to pass. Well to put it simply,

Complexity is inversely proportional to Solution Effectiveness The quicker your solution solves a problem, more effective your solution is or lesser the space you take, better your solution is.

If you are following these posts to begin with competitive programming then before reading further, you should practise evaluating time complexity of solutions from the code itself, at-least cover all the standard ones present in the blogs/books I have mentioned.

Every solution producing correct output is efficient for a given size of input. It is the size of input that forces us to optimise our solutions and reduce the complexity. The higher the size of input, lesser the complexity of solution is expected. Lets see a conversation,

Professor : For given input N, find sum of all natural numbers till N. Student : Haha !! So easy, just run a loop from 1 to N and keep on adding each integer. Solved in O(N)

int sum=0;
for(int i=0;i<N;i++){
sum=sum+i;
}
print(sum)

Professor: Correct, can you solve it for N= 1012
Student : No, Got it. Though the logic is correct, computer won't be able to solve it in seconds. Professor : You have learnt important lesson, great. Student : Yes I need to optimize, I will use direct formula,O(1).

long sum=(N*(N+1))/2;
print(sum);

Student: It will also be limited by N though.Like, N can be taken only enough to fit in memory. Professor : Yes, indeed.But don't worry, problem setters will give solvable problems only.

Thanks, Professor !

Let's see the list of input size of N vs Time complexity efficient enough to solve it.

Now, I have taken this list from this post in Hackerearth since I did not want to duplicate it and it beautifully explains how you should consider constraints as the guideline for the time complexity of expected solution. During initial days of coding, you might want to look at it, eventually with experience you will understand whether your solutions will pass or not by yourself.

Quick Tip

Whichever language you use, learn to compute time taken for your solution, this will help you evaluate your solutions much faster, instead of going to respective coding website and submitting again and again.

For example this can be used as a template for evaluating time in Java.

TimeEvaluationdemo.java
public class TimeEvaluationdemo {
   public static void main(String[] args) {
   double timeStart = System.currentTimeMillis());
   // code here
   double timeEnd = System.currentTimeMillis());
   double timeElapsed = timeEnd - timeStart;
   System.out.time("My program took "+timeElapsed +"ms");
   }
}

I will be starting with basic data structures in my next post, also I am planning to have a video course on competitive coding in collaboration with Twowaits.

Keep coding. All the best!!