1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Anastaziya [24]
3 years ago
11

Suppose that, even unrealistically, we are to search a list of 700 million items using Binary Search, Recursive (Algorithm 2.1).

What is the maximum number of comparisons that this algorithm must perform before finding a given item or concluding that it is not in the list
"Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size n of a problem into n subinstances of size n/3, and the dividing and combining steps take linear time. Write a recurrence equation for the running time T(n), and solve this recurrence equation for T(n). Show your solution in order notation."

Computers and Technology
1 answer:
damaskus [11]3 years ago
7 0

Answer:

There is also an attachment below

Explanation:

Since we are talking about binary search, let's assume that the items are sorted according to some criteria.

Time complexity of binary search is O(logN) in worst case, best case and average case as well. That means it can search for an item in Log N time where N is size of the input. Here problem talks about the item not getting found. So, this is a worst case scenario. Even in this case, binary search runs in O(logN) time.

N = 700000000.

So, number of comparisions can be log(N) = 29.3 = 29.

So, in the worst case it does comparisions 29 times

You might be interested in
Type (dog, cat, budgie, lizard, horse, etc.) Create a class that keeps track of the attributes above for pet records at the anim
Alenkinab [10]

Answer:

If you did the exercise with two Dog objects, it was a bit boring, right? After all, we have nothing to separate the dogs from each other and no way of knowing, without looking at the source code, which dog produced which bark.

In the previous article, I mentioned that when you create objects, you call a special method called a constructor. The constructor looks like the class name written as a method. For example, for a Dog class, the constructor would be called Dog().

The special thing about constructors is that they are the path to any new object, so they are a great place to call code that initializes an object with default values. Further, the return value from a constructor method is always an object of the class itself, which is why we can assign the return value of the constructor to a variable of the type of class we create.

However, so far, we have not actually created a constructor at all, so how come we can still call that method?

In many languages, C# included, the language gives you a free and empty constructor without you having to do anything. It is implied that you want a constructor; otherwise there would be no way of using the class for anything, so the languages just assume that you have written one.

This invisible and free constructor is called the default constructor, and, in our example, it will look like this:

public Dog(){ }

Notice that this syntax is very similar to the Speak() method we created earlier, except that we do not explicitly return a value nor do we even declare the return type of the method. As I mentioned earlier, a constructor always returns an instance of the class to which it belongs.

In this case, that is the class Dog, and that is why when we write Dog myDog = new Dog(), we can assign the new object to a variable named myDog which is of type Dog.

So let’s add the default constructor to our Dog class. You can either copy the line above or, in Visual Studio, you can use a shortcut: type ctor and hit Tab twice. It should generate the default constructor for you.

The default constructor doesn’t actually give us anything new because it is now explicitly doing what was done implicitly before. However, it is a method, so we can now add content inside the brackets that will execute whenever we call this constructor. And because the constructor runs as the very first thing in an object’s construction, it is a perfect place to add initialization code.

For example, we could set the Name property of our objects to something by adding code such as this:

public Dog()

{

   this.Name = "Snoopy";

}

This example will set the Name property of any new objects to “Snoopy”.

Of course, that’s not very useful because not all dogs are called “Snoopy”, so instead, let us change the method signature of the constructor so that it accepts a parameter.

The parentheses of methods aren’t just there to look pretty; they serve to contain parameters that we can use to pass values to a method. This function applies to all methods, not just constructors, but let’s do it for a constructor first.

Change the default constructor signature to this:

public Dog(string dogName)

This addition allows us to send a string parameter into the constructor, and that when we do, we can refer to that parameter by the name dogName.

Then, add the following line to the method block:

this.Name = dogName;

This line sets this object’s property Name to the parameter we sent into the constructor.

Note that when you change the constructor’s signature, you get a case of the red squigglies in your Program.cs file.When we add our own explicit constructors, C# and .NET will not implicitly create a default constructor for us. In our Program.cs file, we are still creating the Dog objects using the default parameter-less constructor, which now no longer exists.

To fix this problem, we need to add a parameter to our constructor call in Program.cs. We can, for example, update our object construction line as such:

Dog myDog = new Dog(“Snoopy”);

Doing so will remove the red squigglies and allow you to run the code again. If you leave or set your breakpoint after the last code line, you can look at the Locals panel and verify that your object’s Name property has indeed been? Got it?

5 0
3 years ago
Which AWS service is a managed service that makes it easy to set up, operate, and scale a relational database in the cloud?​
vaieri [72.5K]

Answer:

I use Google cloud free tier for my Minecraft server

4 0
3 years ago
Think about what you have learned about work ethic. In a paragraph of no less than 125 words, explain why employers prefer to hi
Zepler [3.9K]

An individual who possesses good work ethic embodies principles like reliability, dependability, dedication to the job, teamwork and cooperation, and a self-disciplined character. Most employers seek a strong work ethic; performance depends on it; satisfaction is derived from it; and it ensures career progression. It is that untouchable effort an employee exemplifies daily, regardless of whether someone is watching or not. A company that has its employees doing exemplary well has everything to do with their performance. Thus, if you have a strong work ethic, you will have qualities that will keep you in demand by huge companies. When you are skilled at the workplace and your colleagues notice and appreciate it, you will have a very deep sense of satisfaction within you. If you put 101 percent, your willingness to work hard will be recognized and will leave you shining brightly than others when the opportunity of promotion knocks.

7 0
3 years ago
In this screenshot, the circled item is the
gavmur [86]

Answer:

Favorites tab/bar

Explanation:

6 0
3 years ago
Read 2 more answers
Real numbers which, when squared, become smaller than the original number."
8_murik_8 [283]
Those would be numbers below 1.

Explanation:
.5•.5 = .25
-2•-2 = -4
Hope this helps!
Also consider giving me brainliest.
7 0
2 years ago
Other questions:
  • A typical self-expelling fire extinguisher empties its contents in
    8·1 answer
  • Jason needs to design the colors for a web site that make it easy to read. Which should he consider using?
    9·1 answer
  • The IT department sent out a memo stating that it will start delivering desktop computer interfaces through the IT data center v
    5·1 answer
  • Select the true statement from the choices below. Group of answer choices Invalid code may cause browsers to render the pages sl
    11·1 answer
  • private members of a class are accessible only from _____________ of the same class or from their friends
    12·1 answer
  • Research and build a chroot jail that isolates ssh users who belong to the restrictssh group. (You will also need to create the
    9·1 answer
  • Algorithm to calculate the area of a square.​
    6·1 answer
  • Pleasee helpppppppppppppppppppppp me!
    7·1 answer
  • Explain the term information security?​
    9·1 answer
  • What OC level is primarily used as a regional isp backbone, and occasionally by very large hospitals, universities, or other maj
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!