A community for students.
Here's the question you clicked on:
 0 viewing
anonymous
 one year ago
Have a question about a Quiz 1 answer...
In problem 7.2, it asks, "Under the assumption that logBase2 is O(n), what is the order (use big Oh notation) of f(n)?"
The answer says that it is still O(n), but it seems like it should be O(nlogn), as f(n) has a loop which executes as many times as the logBase2(n) value. Therefore, the call to logBase2(n) will be O(n), and the loop is O(log(n)), so shouldn't the entire function be O(nlogn)?
anonymous
 one year ago
Have a question about a Quiz 1 answer... In problem 7.2, it asks, "Under the assumption that logBase2 is O(n), what is the order (use big Oh notation) of f(n)?" The answer says that it is still O(n), but it seems like it should be O(nlogn), as f(n) has a loop which executes as many times as the logBase2(n) value. Therefore, the call to logBase2(n) will be O(n), and the loop is O(log(n)), so shouldn't the entire function be O(nlogn)?

This Question is Open

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Okay, I hadn't seen Recitation 5 that goes over the answers. The reason that Problem 7.2 on Quiz 1 isn't O(nlogn) is because the O(logn) section of the code is additive with the O(n) section, and so the O(n) dominates. If the program were written in such a way that the O(logn) section were *inside* the code performing the O(n) function, then the entire piece of code would, indeed, be O(nlogn).
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.