A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing


  • 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
  1. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0


  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Okay, 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).

  3. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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...


  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.