Open E-School

Male
Friday, February 24, 1984

Time complexity of an algorithm

Category: Programming Date: Thursday, July 20, 2017

When it comes to algorithms, there are a few very frequently asked questions during interview. One of those questions is about time complexity. The concept of time complexity is helpful in understanding how good an algorithm is. It does not tell you how fast an algorithm is, it just tells you how good an algorithm is.

What is time complexity ?

Majority of the students give a wrong answer to this question. Below are some of the wrong answers which you can give for this question

Wrong answer 1

The time taken by a program to run is known as time complexity

Wrong answer 2

The time taken by a program to complete its core operations is known as time complexity

Wrong answer 3

The time taken by a program to show the output is known as time complexity

Apart from these answers there are many other wrong ways in which you can define time complexity. Please keep in mind that time complexity has just one simple correct definition. If you keep giving wrong answers to this question you will put yourself into trouble.

Right answer

The correct answer to the question what is time complexity is

The increase in the execution time of an algorithm with the increase in the number of data elements is known as time complexity of the algorithm

OR in other words you can also say

The relationship between the execution time of an algorithm and the number of input elements is known as time complexity of the algorithm.

Let us understand the meaning of this definition.

Example 1

Suppose that you want to sort 10 numbers and your algorithm takes 10 seconds to sort them. If you increase the numbers to 20, your algorithm takes 20 seconds to sort them. If you increase the numbers to 50, your algorithm takes 50 seconds to sort them. If you increase the numbers to 100, your algorithm takes 100 seconds to sort them. You can easily notice that the time taken is increasing in direct proportion to the number of data elements. This type of complexity is know as linear time complexity and is denoted by O(n)

Example 2

Suppose that you want to sort 10 numbers and your algorithm takes 100 seconds to sort them. If you increase the numbers to 20, your algorithm takes 400 seconds to sort them. If you increase the numbers to 30, your algorithm takes 900 seconds to sort them. You can notice that the time taken to sort the algorithm is the square of the number of input data elements. This type of complexity is known as quadratic time complexity and is denoted by O(n^2)

With the explanation in this tutorial you must now be able to answer the question about time complexity with confidence.

If you have any questions please ask them by clicking the ask question below.

Rate this article and help us improve

Please Login to rate
Overall ratings: 0 | Rating: out of 5
Previous Article Next Article

Quick Links

E-Magazines

@

Total Followers
Study Group Created
Study Group Joined
Following Teacher
Following Organization
Blog Articles Added
Questions Asked
Questions Answered
Jobs Posted
Total Members in Group
Questions asked by members
Tasks added in this Group

Please wait..

Ok

Login to Open ESchool OR Create your account    Login   SignUp