Practice problems in Algorithm Analysis

• Big-O problems. For each of the following functions, find the best big-O function that bounds it (i.e 3n+7 is O(n). It is also O(n²) but O(n) is a better bound). Justify your answers. Click here to see some example problems
  1. 5n+6-3n
  2. n(n+1)/2
  3. n² + nlog n + 3n
  4. log n + log(n ²)
  5. log n!
  6. 1 + 2 + ... + n
  7. 10000n + 1000
  8. 4n³ + 2n² + 3n + 4
  9. 10n¹⁰⁰
  10. 2ⁿ + 2^n-1
  11. 4n + 5/n
• "How many *" problems Answer the following questions:
  What pattern of *'s do the following programs print?
  How many "*"'s does each of the following programs print?
  Give an exact answer and a big-O answer.

  1.  for i = 1 to 10 do begin
  	for j = 1 to 5 do
  		print "*"
  	print carriage return
      end
  
  2.  for i = 1 to n do begin
  	for j = 1 to n do
  		print "*"
   	print carriage return
      end
  
  3.  for i = 1 to n do begin
  	for j = i+1 to n do 
  		print "*";
  	print carriage return
      end
  
  4.  for i = 1 to n do begin
  	for j = 1 to i do
  		print "*";
  	print carriage return
      end
  

• More code to analyze Answer the following questions.
  What do the following programs print?
  How many times is the while loop executed?
  If we say the running time is the number of print statements executed, what is the running time for each program (in big-O notation)?

  1.  i = 64
      while (i > 1) do begin
  	print i 
  	i = floor(i/2)       /* comment: floor truncates to nearest integer */
      end		             /* less than or equal to the value */
  
  2.  i = n;
      while (i > 1) do begin
  	print i
          i = floor(i/2)
      end
  
  3.  i = 1;
      while (i < n) do begin
  	print i
  	i = i*i
      end
  
  

• Can ignore the next two problems for purposes of the quiz.
• Running time for popular problems For each of the following problems, give the (best possible) worst-case running time in big-O notation. No justification needed.
  1. Adding n numbers
  2. Finding the min of n numbers
  3. Searching in an ordered list of n items
  4. Searching in an unordered list of n items
  5. Sorting n items
  6. Merging two lists each having n items
  7. Finding the median
• Designing algorithms Write an algorithm in pseudocode to solve the following problems.
  1. Finding the min and max in an array of n numbers.
  2. A variant of linear search: Assume the median is precomputed and stored in a variable. Now when you want to search for a particular key, start at the beginning of the list if the key is less than the median and start at the end of the list if the key is greater than the median. (what is the worst-case running time of this algorithm?)
  3. Computing floor(log(n)) by successive divisions.