Scribd Logo
Upload

Welcome to Scribd!

  • 36 views

    Big O Notation (Compatibility Mode)

    Uploaded by

    Ofif Murtessaa
    Big O notation describes how the runtime of an algorithm grows as the input size grows. It analyzes the worst-case scenario and focuses on general trends rather than precise values. Common time complexities include constant O(1), logarithmic O(log n), linear O(n), polynomial O(n^2, n^3), and exponential O(2^n). Faster algorithms like O(1) and O(log n) are preferred to slower ones like O(n^2) and O(n^3).

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Big O Notation (Compatibility Mode)

    Uploaded by

    Ofif Murtessaa
    36 views10 pages
    Big O notation describes how the runtime of an algorithm grows as the input size grows. It analyzes the worst-case scenario and focuses on general trends rather than precise values. Common time complexities include constant O(1), logarithmic O(log n), linear O(n), polynomial O(n^2, n^3), and exponential O(2^n). Faster algorithms like O(1) and O(log n) are preferred to slower ones like O(n^2) and O(n^3).

    Original Title

    big O Notation [Compatibility Mode]

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Big O notation describes how the runtime of an algorithm grows as the input size grows. It analyzes the worst-case scenario and focuses on general trends rather than precise values. Common time complexities include constant O(1), logarithmic O(log n), linear O(n), polynomial O(n^2, n^3), and exponential O(2^n). Faster algorithms like O(1) and O(log n) are preferred to slower ones like O(n^2) and O(n^3).

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    36 views10 pages

    Big O Notation (Compatibility Mode)

    Uploaded by

    Ofif Murtessaa
    Big O notation describes how the runtime of an algorithm grows as the input size grows. It analyzes the worst-case scenario and focuses on general trends rather than precise values. Common time complexities include constant O(1), logarithmic O(log n), linear O(n), polynomial O(n^2, n^3), and exponential O(2^n). Faster algorithms like O(1) and O(log n) are preferred to slower ones like O(n^2) and O(n^3).

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 10

    Big O Notation

    Big O notation – Calculating Algorithm


    Efficiency
    Big O notation is the language we use for talking about
    how long an algorithm takes to run.. It's how we compare
    the efficiency of different approaches to a problem.
    Imagine you have a list of 10 objects, and you want to sort
    them in order. There’s a whole bunch of algorithms you
    can use to make that happen, but not all algorithms are
    built equal.
    It is simply a way of comparing algorithms and how long
    they will take to run.
    Big O notation

    A simplified analysis of algorithm


    efficiency. It considers:
    1. Complexity in terms of input size, N
    2. Machine independence(Doesn’t consider the
    machines hardware)
    3. Basic computer steps
    4. Time & space(working storage) O means order of (German: "Ordnung von").
    n is the input size in units of bits needed to
    represent the input

    General Rules

    Ignore constants (Considers long term


    growth only)
     5n becomes O(n)
    Terms are dominated by others
     O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n)
    < O(n!)
    Ignore lower order terms
    Constant Time Algorithms – O(1)

    Time taken per input size


    Constant time implies that the number
    of operations the algorithm needs to
    perform to complete a given task is
    independent of the input size.
    In Big O notation we use the following
    O(1).
    No matter how much data you add the
    amount of time to perform a task will
    not change.
    The quickest type of algorithm

    Constant time
    O(1) “Big oh of one”

    X = 10 + (5 * 2);
    Input size(X) is independent
     doesn’t matter
     doesn’t effect processing of code/algorithm
    So it’s O(1)
    Constant time
    O(1) “Big oh of one”
    X = 10 + (5 * 2);
    Y = 20 – 2;
    System.out.print(”x + y”);

    Total time is = O(1) + O(1) + O(1) = 3 * O(1)

    Because we drop constants we would call this code


     O(1) “Big oh of one”

    Constant Time Algorithms – O(1)


    Example

    Consider these two bits of code:


    int n = 5000;
    System.out.println("Hey - your input is: " + n);

    int n = 5000;
    System.out.println(“Your input is: " + n);
    System.out.println(“Good stuff with: " + n);
    System.out.println("And more: " + n);

    It doesn’t matter what n is, above. This piece of code takes


    a constant amount of time to run. It’s not dependent on
    the size of n.
    Logarithmic Time Algorithms – O(log n)

    Logarithmic time implies that an


    algorithms run time is proportional
    to the logarithm of the input size.
    In Big O notation this is usually
    represented as O(log n).
    Next fastest after constant time
    Any code that involves a divide
    and conquer strategy
    Binary search algorithm is O(log n)

    Logarithmic Time Algorithms – O(log n)


    Example Logarithm – Basic principle
    How many 2s do we multiply to get 8?
    What is important here is that the running time grows 2x2x2=8
    in proportion to the logarithm of the input (in this So the logarithm is 3
    case, log to the base 2): We would write this as
    log2(8) = 3
    int n = 8;
    for (int i = 1; i < n; i = i * 2){
    System.out.println("Hey - I'm busy looking at: " + i); Any algorithm that ignores
    }
    a proportion of the input
    As n is 8, the output will be the following: data can be considered
    Hey - I'm busy looking at: 1 O(log(n))
    Hey - I'm busy looking at: 2
    Hey - I'm busy looking at: 4

    Our simple algorithm ran log2 (8) = 3 times.


    N = The input value e.g. number
    Because we drop constants we would call this algorithm O(log n) of elements in the array
    Linear Time Algorithms – O(n)

    Next quickest algorithm


    Linear time is a concept
    where by time is seen
    sequentially, as a series of
    events that are leading
    toward something:
    beginning, and an end.
    Grow directly
    proportional to the size
    of its inputs.

    Linear time O(n) example


    This loop prints numbers 0 to n
    Y = 5 + (20 * 20) //O(1)
    For x in range (O, n); //O(N)
     Print x;

    Total time is = O(1) + O(N) = O(N)


    Because Linear time(O(N)) takes so much longer than
    constant time(O(1)) it dominates it and effectively
    becomes irrelevant.
    Linear Time Algorithms – O(n) -
    Example
    for (int i = 0; i < n; i++) {
    System.out.println("Hey - I'm busy looking at: " + i);
    }
    This code runs N times. We don’t know exactly how long it will take for this
    to run – and we don’t worry about that.

    for (int i = 0; i < n; i++) {


    System.out.println("Hey - I'm busy looking at: " + i);
    System.out.println("Hmm..
    ("Hmm.. Let's have another look at: " + i);
    System.out.println("And another: " + i);
    }

    In this second code the runtime would still be linear in the size of its input, n.

    We denote linear algorithms as follows: O(n).

    Polynomial Time Algorithms – O(np)

    Also known as quadratic time


    algorithms
    Normally denoted by nested for
    loops.
    If your array has 10 items and
    your algorithm is running in
    Polynomial time your going to
    be doing 10 * 10 = 100 steps.
    Polynomial Time Algorithms – O(np) - Example

    For x in range (O, n); //O(N)


     Print x;

    For x in range(0, n); //O(N2)


     For y in range (0, n);
     Print x * y; // O(1)

     Three nested for loops? O(N3) Four? O(N4) and so


    on

    Polynomial Time Algorithms – O(np) - Example

    Polynomial is a general term which contains quadratic (n2), cubic (n3), quartic (n4),
    etc. functions.

    for (int i = 1; i <= n; i++) {


    for(int j = 1; j <= n; j++) {
    System.out.println("Hey - I'm busy looking at: " + i + " and " + j);
    }
    }

    Assuming N = 8 this algorithm will run 82 = 64 times


    This is a O(n2) algorithm because it has two loops
    If we were to nest another for loop, this would become an O(n3) algorithm.
    O(n2) is faster than O(n3) which is faster than O(n4), etc.
    Bubble Sort - Polynomial Time Algorithm
    Polynomial Complexity the more data you have the more checks it has to
    make and the more time it will take to run.
    Assuming the data in the array going through the algorithm is not already
    sorted this algorithm would be considered polynomial o(n2). It has two loops.
    If the data is already sorted then the complexity will be linear o(n) because
    the loop only has to run once.
    Enter length of array. (int) Note the big
    100 difference in
    Array contains ’99’ items. execution time based
    I performed ‘4950’ checks on array length.
    Execution time ‘0’ minutes ‘0’ seconds ‘0’ Milliseconds
    Bubble sort is not
    Enter length of array. (int) very efficient for
    60000 larger data arrays.
    Array contains ‘59999’ items. Efficiency decreases
    I performed ‘1799970000’ checks dramatically.
    Execution time ‘0’ minutes ’14’ seconds ‘344’
    Milliseconds

    Cost of running time, acknowledging


    hardware performance as a factor.

    Big O Notation does not consider performance of


    hardware.
    Processor speed, Memory
    emory (Usually RAM),
    bandwidth, latency, storage space, power all have
    an effect on algorithm speed.
    Efficiency of the algorithm of course still plays a
    part but we can’t ignore raw hardware
    performance.

    You might also like