Photo by Markus Winkler on Unsplash

Contents:
  1. Introduction
  2. Algorithm Design

Introduction

Algorithm
The word algorithm comes from a mathematician Al Khwarizmi. Algorithm is a finite set of logical steps made to solve one or more problems. All algorithms should satisfy these criteria:
  • All algorithms should have zero or more inputs.
  • All algorithms should have one or more outputs.
  • All algorithms should have clear and unambiguous instructions/steps.
  • All algorithms should have finite number of steps.
  • All algorithms should have effective instructions/steps.

There are 4 distinct areas in studying algorithms:
  • How to create algorithms?
  • How to validate algorithms?
  • How to analyze algorithms?
  • How to test a program?

Psuedocode
Psuedocode is a descriptive, easier-to-understand version of a computer program/code. It is usually written in English, and uses mathematical notations. Psuedocodes consists of:
  • Variable
  • Iteration / Loop
    • FOR-DO
    • REPEAT-UNTIL
    • WHILE-DO
  • Selection / Branch
    • IF-THEN
    • SELECT-CASE
  • Module
    • Procedure / Sub
    • Function
    • Recursion

Module
Module, or procedure, sub, function, are several lines of algorithm that serves as a function. Module is useful in an algorithms if it is often called/run.

Modules can be called by the main program, other modules, or by itself. When calling modules, it can be done with parameter(s), value, or reference/location.

When a module calls itself, it is a recursion.

Recursion
Recursion is an algorithm that executes itself. This algorithm solves smaller problems before solving the main problem. While recursion can be effective if planned well, it has its own drawbacks. For instance, its memory allocation.

Algorithm Design

Algorithm Steps
The following are the steps of algorithm:
  • Simplify problem
  • Build plans to solve it mathematically
  • Design the algorithm
  • Test/validate the algorithm
  • Express algorithm in a programming language
  • Document
  • Analyze complexity of algorithm

Algorithm Processing Time
Algorithm processing time, pretty much, is the time needed by a computer to run an algorithm. When running an algorithm with a powerful computer, it becomes harder for us to notice the processing time of the algorithm. Not all algorithms can be run in less than a second. Even a powerful computer needs a minute, or days to run a complex algorithm. It can be concluded that it is important to calculate processing time when designing a complex algorithm. The performance of an algorithm is usually measured through the use of a benchmark for the worst case, which is the Big-O notation.

An algorithm works based on the user input(s). The larger the input is, (usually) the longer time the algorithm will need. The processing time is classified into:
  • Best case, written as θ()
  • Average case, written as Ω()
  • Worst case, written as O()

The following are the time complexity of some common operation/algorithm:
Time Complexity Operation
Operations that don't rely on input size such as assigning values to a variable, accessing an array's element, performing mathematical operation on a variable.
Operations whose operation time is directly proportional to the logarithm of logarithm of its input size: single loop with variable is exponentially multiplied by a constant.
Operations whose operation time is directly proportional to the logarithm of its input size: single loop with variable multiplied/divided by a constant in each iteration. It can be said that performing binary search belongs in this category.
Operations whose operation time is directly proportional to its input size: single loop with variable incrementing/decrementing by a constant in each iteration. It can be said that printing all elements of one dimensional array with size n and performing linear search belongs in this category.
Operations whose operation time is directly proportional to its input size to the power of x: x-nested loops. It can be said that for , printing all elements of two dimensional array with size n2, performing bubble sort, insertion sort and selection sort belongs in this category.


Suppose is a polynomial with highest degree . Then, it can be said that