0

I've gotten this question for an assignment in our introduction to computer science. And I have absolutely no idea on how to solve it. Help very much appreciated!!
This may sound like a cliché, but my girlfriend just left me, so I can't think straight even though how hard I try, and I have to deliver this by tommorow..

Question:
Design an algorithm for finding the cubic root of a positive integer,
rounded down to the nearest integer. Thus, given input N, a positive
integer, you should find a positive integer m such m^3 is smaller or equal to N, but (m + 1)^3 > N. Use the binary search idea.

(a) Express the algorithm in pseudocode.
(b) Find a fundamental operation and use big theta notation to ex-
press how long your algorithm takes. Express this as a function
of the positive integer N which is input, and also as a function of
the length of N (the number of bits in N). State any assumption
you make about how long it takes to multiply two integers, one of
length s and one of length t.

2
Contributors
1
Reply
2
Views
6 Years
Discussion Span
Last Post by Momerath
0

This is the same problem as the "guess the number" game. You pick a range to search in that you know the number (in this case, the cube root) exists. You then divide this range in half, and determine which half the number exists in. Repeat dividing in half until you have the number you are searching for.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.