CIT 596 - HW1 - 2025
1. (5 points) For the following functions, how would you express them in terms of the big- O notation. You do not need to provide any explanation. Your answer has to be written in the most compact manner possible. An answer of O(50n + 20) will receive 0 points. In that case we would be expecting an answer of O(n).
If not specified, you can assume the base for logarithm is 2.
• 100n2 + 25n3 + 10000n2 log n
• log n + log n2 + log(log n)
• n3 + 3n + n!
• 2n+1 + n101
• log5 (n3 ) + 2log2 n
• 3log2 (n) + 17n2
2. (10 points) Formally prove that 5nlog2 n + 7n − 5000 is Θ(nlog2 n).
3. (5 points) When we say an algorithm is O(log n) (or even Θ(log n)) we are allowed to be sloppy about the base of the logarithm (we do not write it usually). Why is this OK?
We are looking for mathematical reasoning in this question, so please use definitions, formulae, theorems etc.
4. (5 points) We have a simple undirected graph (a graph with a finite number of vertices and at most one edge between any pair of vertices). Let m be the number of edges and n be the number of vertices. Person X tells you that they have an algorithm for accomplishing a certain graph theoretic task that runs in Θ(n2 ). Person Y tells you that they have an algorithm for accomplishing the same task that is running in time Θ(m).
Who has the better algorithm in terms of runtime? As the graph gets larger and larger, whose algorithm is likely to be faster. Please provide a brief explanation here.
When considering which algorithm is better, you might want to think about different types of graphs - graphs with many edges, graphs with less edges. . ..
5. (5 points) Solve this recurrence by expanding it out.
Please express your answer in big-O notation. Please show your work.
Note that you will need to know the formula for the sum of the first n natural numbers for this question.
6. (3 points) A recursive algorithm for checking whether or not a string is a palindrome can be described in plain English in the following manner.
Base case - If it is single character string or empty string, it is clearly a palindrome.
Check whether the first character and the last character are the same. If they are not, return false. If they are the same, then recursively check whether the substring from the 2nd character to the penultimate character (second last) character is a palindrome.
Write a recurrence that describes the runtime of this algorithm (this is the T(n) equa- tion). Please explain how you got that recurrence equation. You are not required to solve the recurrence.