Quadratic Time Complexity O(nc)
The time complexity is defined as an algorithm whose performance is directly proportional to the squared size of the input data, as in nested loops it is equal to the number of times the innermost statement is executed. For example, the following sample loops have O(n2) time complexity
Quadratic time complexity, denoted as O(n^2), refers to an algorithm whose running time increases proportional to the square of the size of the input. In other words, for an input of size n, the algorithm takes n * n steps to complete the operation. An example of an O(n^2) algorithm is a nested loop that iterates over the entire input for each element, performing a constant amount of work for each iteration. This results in a total of n * n iterations, making the running time quadratic in the size of the input.
C++
// Here c is any positive constantfor (int i = 1; i <= n; i += c) { for (int j = 1; j <= n; j += c) { // some O(1) expressions }}for (int i = n; i > 0; i -= c) { for (int j = i + 1; j <= n; j += c) { // some O(1) expressions }}for (int i = n; i > 0; i -= c) { for (int j = i - 1; j > 0; j -= c) { // some O(1) expressions }}// This code is contributed by Kshitij |
C
for (int i = 1; i <= n; i += c) { for (int j = 1; j <= n; j += c) { // some O(1) expressions }}for (int i = n; i > 0; i -= c) { for (int j = i + 1; j <= n; j += c) { // some O(1) expressions }} |
Java
for (int i = 1; i <= n; i += c) { for (int j = 1; j <= n; j += c) { // some O(1) expressions }} for (int i = n; i > 0; i -= c) { for (int j = i + 1; j <= n; j += c) { // some O(1) expressions }}// This code is contributed by Utkarsh |
C#
using System;class Program { static void Main() { // Here c is any positive constant int n = 10; // You can replace 10 with your desired // value of 'n' int c = 2; // You can replace 2 with your desired // value of 'c' // First loop for (int i = 1; i <= n; i += c) { for (int j = 1; j <= n; j += c) { // some O(1) expressions Console.WriteLine("Expression at (" + i + ", " + j + ")"); } } // Second loop for (int i = n; i > 0; i -= c) { for (int j = i + 1; j <= n; j += c) { // some O(1) expressions Console.WriteLine("Expression at (" + i + ", " + j + ")"); } } // Third loop for (int i = n; i > 0; i -= c) { for (int j = i - 1; j > 0; j -= c) { // some O(1) expressions Console.WriteLine("Expression at (" + i + ", " + j + ")"); } } }} |
Javascript
for (var i = 1; i <= n; i += c) { for (var j = 1; j <= n; j += c) { // some O(1) expressions }}for (var i = n; i > 0; i -= c) { for (var j = i + 1; j <= n; j += c) { // some O(1) expressions } } |
Python3
for i in range(1, n+1, c): for j in range(1, n+1, c): # some O(1) expressionsfor i in range(n, 0, -c): for j in range(i+1, n+1, c): # some O(1) expressions # This code is contributed by Pushpesh Raj |
Example: Selection sort and Insertion Sort have O(n2) time complexity.
How to Analyse Loops for Complexity Analysis of Algorithms
We have discussed Asymptotic Analysis, Worst, Average and Best Cases and Asymptotic Notations in previous posts. In this post, an analysis of iterative programs with simple examples is discussed.
The analysis of loops for the complexity analysis of algorithms involves finding the number of operations performed by a loop as a function of the input size. This is usually done by determining the number of iterations of the loop and the number of operations performed in each iteration.
Here are the general steps to analyze loops for complexity analysis:
Determine the number of iterations of the loop. This is usually done by analyzing the loop control variables and the loop termination condition.
Determine the number of operations performed in each iteration of the loop. This can include both arithmetic operations and data access operations, such as array accesses or memory accesses.
Express the total number of operations performed by the loop as a function of the input size. This may involve using mathematical expressions or finding a closed-form expression for the number of operations performed by the loop.
Determine the order of growth of the expression for the number of operations performed by the loop. This can be done by using techniques such as big O notation or by finding the dominant term and ignoring lower-order terms.
Contact Us