CS 2420 — Big O Notation Problems
I am studying Computer Science at the University of Utah. To review for my first mid term in CS 2420 (Data Structures and Algorithms), I will be writing stories here about the problems from the review study guide. Super Exciting stuff right?! Well at least some of it will be so stay tuned. I hope the one person who makes it to this story enjoys it ;).
- What is the Big-O complexity of a function with runtime: 1000N + N/2 + log(N) ∗ N?
When I look at this problem, I first focused on log(N) * N. I believe the multiplication here signifies nested for loops or something like that. This produces NLog(N) term. The other terms 1000N and N/2 do not factor in as N -> very, very big. So I believe that NLog(N) is the Big-O notation of O(N*Log(N)). It is basically limits.
This is the answer from the solutions of the review.
2. What is the BigO complexity of a function with runtime: (N²/N) + N?
This problem can be simplified first before analyzed. (N²/N)+ N -> N + N -> 2N. Now that I have it simplified to 2N, the Big-O notation is very easy as there is only one term left. The constant before N is ommited in the Big-O notation, this leaves the answer O(N).
This also turns out to be the answer from the solutions to the review.
These are the first few questions from the mid term review and my thought process as I was answering them. Yep fun stuff. Apparently 1/3 of the students will fail this class, so this is a pretty important test.