Running Time of Algorithms

Running Time of Algorithms

The running time of an algorithm for a specific input depends on the number of operations executed. The greater the number of operations, the longer the running time of an algorithm. We usually want to know how many operations an algorithm will execute in proportion to the size of its input, which we will call N.

What is the ratio of the running time of Insertion Sort to the size of the input? 

Example:

Input:  n=5, arr[]={2,1,3,1,2}
Output: 4

Approach

Java

public class RunningTimeAlgorithms {
    public static void main(String[] args) {
        int[] arr = { 2, 1, 3, 1, 2 };
        System.out.println(runningTime(arr));
    }

    static int runningTime(int[] arr) {
        int n = arr.length;
        int cnt = 0;
        for (int i = 1; i < n; i++) {
            int x = arr[i];
            int j = i;
            while (j > 0 && arr[j - 1] > x) {
                arr[j] = arr[j - 1];
                j--;
                cnt++;
            }
            arr[j] = x;
        }
        return cnt;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

int runningTime(vector<int> arr)
{

    int n = arr.size();
    int cnt = 0;
    for (int i = 1; i < n; i++)
    {
        int x = arr[i];
        int j = i;
        while (j > 0 && arr[j - 1] > x)
        {
            arr[j] = arr[j - 1];
            j--;
            cnt++;
        }
        arr[j] = x;
    }
    return cnt;
}

int main()
{
    int n = 5;
    vector<int> arr = {2, 1, 3, 1, 2};

    cout << runningTime(arr);
    return 0;
}