Java

TOPIC i06 – ALGORITHM COMPLEXITY & THE BIG O NOTATION

 

LESSON WORK

 

 

QUESTION 1

Simplify the following:

 

a)    O(n + 5)

b)    O(n2 – 13)

c)     O(n5 + n4)

d)    O(n2 + 2n2 + 4n)

e)    O(n/5 + n3)

 

QUESTION 2

Express the complexity of the following algorithms using Big O notation.

 

a)

 
public static boolean IsFirstElementNull(String[] s)
{
        if(s[0] == null)
        {
               return true;
        }
        return false;

}

b)

 
public boolean contains(String[] s, String v)
{
        for(int i = 0; i < s.length; i++)
        {
               if(s[i] == v)
               {
                       return true;
               }
        }
        return false;
}
 
Note: For Big O Notation, we consider the worse case scenario.

c)

 
public boolean containsDuplicates(String[] s)
{
        for(int i = 0; i < s.length; i++)
        {
               for(int j = 0; j < s.length; j++)
               {
                       if( i != j && s[i] == s[j])
                       {
                               return true;
                       }
               }
        }
        return false;
}