Either you can download the handwritten notes in pdf (Link is given at the end of the page) or you can read them on this site itself.
Once we are able to write the runtime in terms of the size of the input (n), we can find the time complexity.
For example, T(n) = n^{2} → O (n^{2})
T(n) = log n → O (log n)
Some tricks to calculate the complexity
In most cases, we try to represent the runtime in terms of the input which can be more than one in number. For example,
Painting a park of dimension m * n → O (mn)
2. Fine the time complexity of the func function in the program from program2.c as follows:
3. Consider the recursive algorithm above, where the random(int n) spends one unit of time to return a
random integer which is evenly distributed within the range [0,n][0,n]. If the average processing time
is T(n), what is the value of T(6)?
4. Which of the following are equivalent to O(N)? Why?
a) O(N + P), where P < N/9
b) 0(9N-k)
c) O(N + 8log N)
d) O(N + M2)
5. The following simple code sums the values of all the nodes in a balanced binary search tree. What is its
runtime?
6. Find the complexity of the following code which tests whether a give number is prime or not?
7. What is the time complexity of the following snippet of code?
You can download the notes by simply clicking on this below download link. :)
Any Course related announcements will be posted here
Be the first person to comment!