Time Complexity in Programming

Have you ever come across the terms complexity and scale while reading a programming book or an article and didn't have an idea or thorough understanding of what complexity and scale mean in terms of programming, then this article is for you.

Today we are going to talk about what does complexity and scale mean?

Scale:

Scale means different in different scenarios like in a database your database is attributed to being scaleable if it reads and writes efficiently with less execution time. Architecture is attributed to being scalable if it can easily add new features/functionalities. Lastly, you can measure the scale for your program/algoritham by understanding the following two terms.

• Time Complexity.
• Space Complexity.

Time Complexity:

"Time complexity means how much time your progam takes to execute based on the input your program takes"

This could be done by noticing the time before and after the function executes and calculating the difference between start and end time. But, imagine, the interviewer asks you about the complexity of a program that will sum the number from 0-n and doesn't allow you to do the above-mentioned steps. Big-O notation to your rescue here by understanding it you can easily tell the interviewer how much time will the program takes in average case scenario.Usually, we calculate the algorithmetic complexity by the lines in our programs and loops. Let's understand this by following snippet:

Types Of Time Complexity:

• Constant Time Complexity.
• Linear Time Complexity.
• Quadritic Time Complexity.
• Logarithmic Time Complexity.
• Quaslinear Time Complexity.

Constant Time Complexity:

Any program which have same execution time irrespective of the input data size is said to be constant time complexity program. For example consider the following piece of code.

Linear Time Complexity:

Any program which increases it's execution time linearly with increase in input data size is said to be linear time complexity program.We represent linear time complexity by O(n) notation. Lets see an example to better understand this.

As the time increases with input size, means for this algorithams time is directly proptional to input size. So thats why it is Linear time complex program.

Quadritic Time Complexity:

Any program/algoritham which have one level nested loop is said to be quadritic time complex.Let's see an example.

Logarithmic Time Complexity:

Any algoritham which works on subset of input data based on some assumptions is said to be logarithmic time complex. Let's understand it by an example.

Quaslinear Time Complexity:

Algorithams which uses different algorithams internally based on the amount of input to solve the problem are said to be Quaslinear. Suppose that you are writing sort function and you decided to use the insertion sort for larger data set and Quick Sort for larger data set because of xyx reason than the alogritham will have time complexity of O(n log n). This algorithams behave better than linear time but are less effecient than logarithmetic.

Important things to keep in mind:

• Big-O notation is for average case,
• Big Omega notation is for best case.
• Big theta notation is for worst case.