Algorithm Basics

Characteristics

1. Input ⇒ An algorithm should take finite number of inputs.
   • It is essential for any algorithm before starting.
   • Input should be given to it initially before the Algorithm begins.
2. Output ⇒ An algorithm must give at least one required result from the given set of input values. These output values are known as the solution to a problem.
3. Definiteness ⇒ Each step should be unique
   • No step should be repeated
   • Each step must be clear and precisely defined.
4. Finiteness ⇒ It means algorithm should be terminated after a finite number of steps.
   • Also, each step should be finished in a finite amout of time.
5. Correctness ⇒ Output should be correct.

Types of algorithm

1. Sequential algorithms are a type of algorithm that executes a set of instructions in a fixed order, one after the other.
2. Conditional algorithms are a type of algorithm that executes different sets of instructions based on certain conditions.
3. Looping algorithms, also known as iterative algorithms, are a type of algorithm that repeats a set of instructions multiple times until a certain condition is met.

Example

Algorithm to swap two numbers without using third variable ↓

                    
step 1. input a and b 
step 2. a = a + b
        b = a - b
        a = a - b
step 3. print a and b
                    
                

Algorithm to find largest number in an array ↓

                    
step 1. input size 
step 2. input elements in an array arr[size] 
step 3. largest = arr[0] and i = 0
step 4. repeat step 5 while i <= size 
step 5. if(arr[i] > largest)
            largest = arr[i] 
        end of if
        i = i + 1;
step 6. print largest
                    
                

Algorithm to delete an element from an array ↓

                    
A is an Array 
pos is the location of the element to be deleted
N is the size of the array 
E is the element to be deleted
deletion(A, pos, N)
step 1. E = A[pos]
step 2. for i = pos to N - 1 repeat step 3 
step 3. A[i] = A[i+1]
        end of for loop
step 4. N = N - 1
                    
                

Algorithm to reverse an character array ↓

                    
S is the character array 
L is the length of the character array 
start is the pointer pointing to first element 
end is pointing to last element 
swap(S, L)
step 1. repeat step 2 while start < end 
step 2. temp = S[start]
        S[start] = S[end]
        S[end] = temp 
        start = start + 1
        end = end - 1
step 3. print S [reversed character array]
                    
                

Time complexity of Algorithm

• Time complexity of an algorithm is the amount of time (or the number of steps) needed by a program to complete its task (to execute a particular algorithm.)
• The time taken for an algorithm is comprised of two times:
  1. Compilation time
  2. Run time
• Compile time
  • Compilation time is the time taken to compile an algorithm.
  • While compiling it checks for the syntax and semantic errors in the program and links it with the standard libraries.
• Run time
  • It is the time to execute the compiled program.
  • The run time of an algorithm depend upon the number of instructions present in the algorithm.
  • Note that run time is calculated only for executable statements and not for declaration statements.

Types of Time Complexity

• Time complexity of an algorithm is generally classified into three types.

                        
step 1. input n 
step 2. result = 0, i = 1
step 3. repeat step 4 while i <= n 
step 4. result = result + i 
        i = i + 1
step 5. print result 
                        
                    

Space complexity

• Space complexity is a measure of the amount of memory space required by an algorithm to solve a problem.
• It is typically expressed in terms of the amount of memory space used by an algorithm in relation to the input size. In other words, it is the amount of memory used by an algorithm to store the data structures and other variables used during the execution of the algorithm.
• To calculate the space complexity of an algorithm, we can use the Big O notation, which expresses the upper bound of the growth rate of the space used by the algorithm. For example, if an algorithm has a space complexity of O(n), it means that the amount of space used by the algorithm grows linearly with the input size. Similarly, if an algorithm has a space complexity of O(n^2), it means that the amount of space used by the algorithm grows quadratically with the input size.

O(1): Constant Time

• When your algorithm is not dependent on the input size n, it is said to have a constant time complexity with order O(1).
• This means that the run time will always be the same regardless of the input size.
• Examples:
  • Accessing Array index (int a = Arr[5];)

O(n): Linear Time

• When the running time of an algorithm increases linearly with the size of the input.
• This means that when a function has an iteration that iterates over an input size of n, it is said to have a time complexity of order O(n).

                       
// factorial program 
int calcFactorial(int n)
{
    int ,factorial = 1, i;
    for(i = 0; i <= n; i++)
    {
        factorial = factorial * i;
    }
    return factorial;
}
                       
                   

• The fact that the runtime depends on the input size means that the time complexity is linear with the order O(n).

Here the programs like inserting, printing array elements have the O(n) complexity.

O(n²): Quadratic Time

• When there is nested iteration, meaning having a loop in a loop and inner loop is dependent on outer loop, here the time complexity is quadratic, which is horrible.
• A perfect way to explain this would be if you have an array with n items. The outer loop will run n times, and the inner loop will run n times for each iteration of the outer loop, which will give total n² prints. If the array has ten items, it will print 100 times (10²).

O(log n): Logarithm Time

• This is similar to linear time complexity, except that the runtime does not depend on the input size but rather on half the input size.
• When the input size decreases on each iteration or step, an algorithm is said to have logarithmic time complexity.
• Certain divide and conquer algorithms based on linear functionality.
• This method is the second best because programs run for half the input size rather than the full size. After all, the input size decreases with each iteration.
• A great example is binary search functions, which divide your sorted array based on the target value.

                                       
// binary search
int binarySearch(int arr[], int size, int target)
{
    int low = 0;
    int high = size - 1;
    int mid;
    while(low <= high)
    {
        int mid = (low + high)/2;
        if(arr[mid] == target)
        {
            return mid;
        }
        if(arr[mid] > target)
        {
            high = mid - 1;
        }
        else 
        {
            low = mid + 1;
        }
    }
    return -1;
}
                       
                   

O(n log n)

• Examples:
  • Merge sort
  • Heap sort
  • Quick sort

Practise questions

1. Find the time complexity of the func1 function in the program shown below ↓

2.

3. Find the complexity of the following code which tests whether a given number is prime or not?

4. What is the time complexity of the following snippet of code?