Exercise 1. Please show the big O notation of the recurrence relation below (ple

Question

Exercise 1. Please show the big O notation of the recurrence relation below (please show detailed steps for full credits): T(n) = T(n-1) + n

Exercise 2. What is the big O notation of the following program (please show detailed steps for full
credits):
for (int i=n; i>0; i-=2)
for (int j=i; j<n; j++)
{//other constant time statements ;}

Exercise 3. Write a java program that prompts the user to enter a string and displays the maximum consecutive increasingly ordered substring. For example, if the input string is "abcabcdgabmnsxy", then the maximum increasingly ordered substring is "abmnsxy". Analyze the time complexity of your program.

Hint. charAt(int i) returns the character of the current String object at index i. For example: "soMeStriNG".charAt(2) returns ‘M’.

Exercise 4. Find the non-recursive version of the following recursive function. Which version is better?

static long tough(int x, int y) {

if (x < y) return tough(y, x);

else if ( y <= 0 ) return 1;

else { if (x > y) return tough(x - 1, y) + tough(x - 1, y - 1);

else // it means x == y return tough(x - 1, y - 1);

}

}

Explanation / Answer

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Exercise => 3

package my_chegg_package;
import java.util.HashMap;
import java.util.Collections;
import java.util.Map;
import java.util.Scanner;
public class chegg_class_one {
   public static void main(String[] args)
   {
   Map<String,Integer> stringMap = new HashMap<String,Integer>();  
    Scanner scan = new Scanner(System.in);
    /* here we take input string from user */
    System.out.print("Enter the String ");
   String s = scan.next();
   String t="";
   int len=0;
   for(int i=0;i< s.length()-1;i++)
   {
       if((s.charAt(i+1)- s.charAt(i))> 0)
       {
             t = t + s.charAt(i) ;
             len=len+1;
       }
       else
       {
           t = t+ s.charAt(i);
           len=len+1;
           stringMap.put(t,len); /* here we insert substrings with respect to their lengths in hashmap*/
           len=0;
           t="";
       }
       if(i == s.length()-2)
       {
           if(s.charAt(s.length()-1)- s.charAt(s.length()-2) > 0)
           {
               t=t+s.charAt(i+1);
               len=len+1;
               stringMap.put(t,len);
           }
           else
           {
               t="";len=0;
               t=t+s.charAt(i+1);
               stringMap.put(t,len);
           }
       }  
   }
   int maxValueInMap=(Collections.max(stringMap.values())); /* This will return max value in the Hashmap */
     for (java.util.Map.Entry<String, Integer> entry : stringMap.entrySet()) {
         if (entry.getValue()==maxValueInMap) {
            System.out.println(entry.getKey());     /* Print that maximum increasingly ordered substring */
         }
}
   }

}

==================== OUTPUT

Enter the String ---> abcabcdgabmnsxy

OUTPUT -----------> abmnsxy

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

Exercise => 2

according to given question -

T(n) = T(n-1) + n

T(n)   - T(n-1) = n

similarly like above step ,

T(n-1) - T(n-2) = n-1

T(n-2) - T(n-3) = n-2
...
...
T(2)   - T(1)   = 2
T(1)   - T(0)   = 1

now ,Summing all above equations -

T(n) - T(0) = 1 + 2 + ... + (n-1) + n = n * (n+1) / 2 = O(n ^ 2)

-------------------------------------------------------------------------------------------------------------------------------------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.