Create FREE 'HowTo' Videos with MyGuide

Algorithms



Pass Quiz and Get a Badge of Learning



Content "filtered", Please subscribe for FULL access.


Chapter 9 : Algorithms and Big-O Notation


Algorithms arrow_upward


  • An Algorithm is a sequence of unambiguous instructions for solving a problem.
    • Used to obtain a required output for any legitimate input in a finite number of steps.
    • Algorithms can be expressed in many ways, including natural languages, pseudo code, flowcharts and programming languages.

    Algorithm Flow arrow_upward


  • An exact specification or procedure for solving a computational problem.
  • Expressed as a finite sequence of steps.
  • It must specify each and every step completely.
  • A machine can implement it.
  • It must work for all possible inputs.

  • Example of Algorithm Flow arrow_upward

  • Algorithms must be:
    • Correct: For every possible input.
    • Efficient: Run quickly, and use as little memory as possible.

    Example of a Simple Algorithm arrow_upward


  • Algorithm for calculating the average of two numbers:

  • Steps

    Task

    Start

    Step 1

    Input any 2 Numbers

    Step 2

    Add both numbers

    Step 3

    Divide the result by 2

    Step 4

    Return result of step 3

    End


    Steps of Algorithm Development arrow_upward


    Steps

    Description

    Identify the Inputs

  • What type of data is needed?
  • How will the program get that data?
  • What will be the format of the data?
  • Identify the Processes

  • How will the program manipulate the data to produce meaningful results?
  • Identify the Outputs

  • What outputs should be returned?
  • What form will the outputs take?

  • Analysis of Algorithms arrow_upward


  • The performance of algorithms can be influenced by several factors:
    • Size of input.
    • Speed of the machine which will run it.
    • Language in which it will be implemented.
    • Efficiency of the compiler that will create the program.

    Runtime Analysis arrow_upward


  • T(n), running time of a particular algorithm on input of size n
  • Provides the number of times the instructions in the algorithm are executed.

  • Big O Notation arrow_upward


  • A sorting algorithm would take longer to sort 100,000 elements than 100.
    • How can we compare performance of two sorting algorithms?
    • Roughly, how much time will it take?
    • We use Big O notation.
  • Used to describe the performance or complexity of an algorithm.
    • Provides information on how long it will take to run according to the size of the input ā€œnā€.
  • Provides an answer to the question "roughly how much time?"
  • It is used by computer scientists to describe algorithms.

  • O (1)

  • O (1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.
  • If a program takes 100 seconds irrespective of input size then its time complexity is O(1).

  • O (n)

  • O (n) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.
  • If a program takes 1 second for input size less than 100, then after the size goes beyond 100, if the time taken increases linearly with respect to input size then its time complexity is O (n).

  • O (n2 )

  • O (n2 ) represents an algorithm whose performance is directly proportional to the square of the size of the input data set.

  • Thank You from Kimavi arrow_upward


  • Please email us at Admin@Kimavi.com and help us improve this tutorial.


  • Mark as Complete => Receive a Certificate in Data-Structure


    Kimavi Logo

    Terms and conditions, privacy and cookie policy | Facebook | YouTube | TheCodex.Me | Email Kimavi


    Kimavi - A Video Learning Library { Learning is Earning }

    Get Ad Free Learning with Progress Report, Tutor Help, and Certificate of Learning for only $10 a month



    All videos on this site created using MyGuide.

    Create FREE HowTo videos with MyGuide.