1. COMP.CS.300 Data Structures and Algorithms 1 »
  2. Course week 4 - Big-O, -Omega and -Theta »
  3. Course week 4

Course week 4

Self-study

The topics for this week are as follows are all related to Asymptotic analysis and algorithm efficiency: (i) Big-O, Big-Omega, Big-Theta (ii) Best case, worst case, average case

The following links will take you to the video-lectures and the accompanying slides:

Algorithm efficiency of Mergesort and Quicksort

slides for Algorithm efficiency of Mergesort and Quicksort

Week04 - Glossary

What can we use the big-O notation ( \(O\) ) to describe?
Suppose an algorithm’s running time function is \(f(n)\) and we know that \(f(n)\) belongs to \(O(1)\). Which of the following statements is true?
What can we use the big-Omega notation ( \(\Omega\) ) to describe?
Suppose that algorithms A and B can be used to compute the same thing. Which of the following statements is true? (More than 1 may be true.)
Suppose an algorithm’s running time function is \(f(n)\) and we know that \(f(n)\) belongs to \(O(n)\). Which of the following statements is true? (More than one may be true.)
Suppose an algorithm’s running time function is \(f(n)\) and we know that \(f(n)\) belongs to \(O(g(n))\) and also to \(\Omega(h(n))\). Which of the following statements is always true?
Which statement is true for insertion sort?
Suppose array \(A\) is input into insertion sort and suppose insertion sort outputs array \(A\) whose elements are sorted from smallest to largest. What is the worst case input \(A\)?
Suppose we have an array \(A\) with numbers. For this collection of numbers let \(A_{best}\) and \(A_{worst}\) correspond to the best and worst input cases for insertion sort. Which of the following is true?
MERGESORT is called with an input array \(A\) having \(n\) elements. Of the following, which is the best upper bound on the number of recursion levels that MERGESORT will use?
Suppose the asymptotic runtime efficiency of QUICKSORT is analyzed when the starting array \(A\) has \(n\) elements. Which of the following are true?
Suppose MERGESORT, QUICKSORT and INSERTIONSORT are being compared. Which of the following are true? (There may be more than one true statement.)
What is a central question, related to this course, whose answer can be found in this week’s videos?
Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?
Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

Week04 - Glossary

Viikko04 - Sanasto

Submit weekly exercises

Questions to be submitted this week