I am so confused on how to tell a run time of a algorithm. so i came up with some ex for me to understand. could any one tell me if i am find the run time right plz.

ex1 - run time for this loop is O(n)? bc it going to loop through n times.

    for(i = 0; i < n; i++)
    {
       //do some thing
    }

ex2 - O(n-1)? bc it going to loop through n-1 times.

    for(i = 0; i < n-1; i++)
    {
        //do some thing
    }

ex3 - O((n)(n)) bc n times n

   for(i = 0; i < n; i++)
   {
       for(x = 0; x < n; i++)
           {
           //do some thing
           }
   }

ex4 - to find value from sorted array is O(n) bc it would run n times.

    int a[n] = {1,2,3,4};
    int x = 2;
    for(i = 0; i < n; i++)
    {
        if(a[i] = x)
        {
            //do some thing
        }
    }

ex5 - to find value from UNSORTED array also is O(n) bc it would run n times.

    int a[n] = {4,3,1,2};
    int x = 2;
    for(i = 0; i < n; i++)
    {
        if(a[i] = x)
        {
            //do some thing
        }
    }
  1. yes
  2. O(n-1) = O(n)
  3. yes, although you probably made a typo here: for(x = 0; x < n; i++) instead of x++
  4. yes, assuming you use the algorithm as in your example
  5. yes, assuming you use the algorithm as in your example

Some additional info:
O(n) means the worst case running time. So assume that you have an array of length n, you need to find an element and you use the algorithm as in your example 4 and 5. The worst case is that the element is at a[n-1], meaning that you had to run the loop n times in total (including the time that you found the element).

Edited 4 Years Ago by Kashaku: additional info

This article has been dead for over six months. Start a new discussion instead.