0
6.4kviews
What is time complexity? Determine the time complexity of the following code

Please find the code snippet below

for(i=1; i<=n; i++)

for(j=1; j<=n; j++) x=x+1

2 Answers
3
154views

The amount of time taken by an algorithm to run as a function is known as time complexity. It measures the time taken to execute each statement of code in an algorithm. It is calculated by counting the number of basic steps taken by any algorithm to complete execution. The three concepts below, known as Asymptotic Notations, can be used to indicate time-complexity:

Big – O (Big Oh): It is the total amount of time an algorithm takes for all input values. It depicts an algorithm’s worst-case time complexity.

Big – Ω (Omega): It gives the minimum time required by an algorithm for all input values. It is the best case scenario for an algorithm’s time complexity.

Big – Θ (Theta): It specifies the average bound of an algorithm and represents the average case of an algorithm’s time complexity.

Complexity of the code

for(i=1; i<=n; i++)--------------this will go for n times

for(j=1; j<=n; j++)-------------this will go for n times

Since the 2nd loop is nested in 1st then the complexity of overall code will be n*n. Hence, the time complexity of the code is O(n2).

1
114views

There can be many algorithms(ways) to solve a problem and every solution we obtain from all the ways is the same. So, to decide on which algorithm to use or to choose the way to apply for a problem ,time complexity comes into picture.

Time Complexity : It is the amount of time taken by any function or algorithm to complete its task, It can be applied to any function or algorithms, but most importantly to Recursive functions .

There is a concept called Asymptotic Notations which are used for analyzing the best case and worst case performance of an algorithm by its inputs .They include:

• Big-O Notation (O-notation) : Big O notation is a way to describe the speed or complexity of a given algorithm. We`ll use Big O notation to compare different algorithms by the number of operations they make. Big O establishes a worst-case run time.

• Omega Notation (Ω-notation) :Similar to big O notation, big Omega(Ω) function is used in computer science to describe the performance or complexity of an algorithm. Ω-notation establishes a Best-case run time.

• Theta Notation (Θ-notation) : In general, we always want to give a theta bound if possible because it is the most accurate and tightest bound. Θ-notation establishes Average-case run time . Now finding the complexity of the code given:

for(i=1; i<=n; i++)

for(j=1; j<=n; j++) x=x+1

Line 1 will runs n times. The time complexity becomes O(n). Line 2, the inner loop will run a max of n-1 times for each outer loop iteration. Time complexity is O(n-1) = O(n) Line 3 is of constant complexity O(1).

Total time complexity is $O(n) * O(n) * O(1) = O(n^2)$

Please log in to add an answer.