I think you are right, though, in that they meant to initialize ##j## as ##1## and have ##i## increment in each of its loop's iterations, in which case:
##\rm{foo}## is executed ##n## times
##\rm{bar}## is executed ##n \log_2 n## times
##\rm{qux}## is executed ##n^2 \log_2 n## times
The...
Good point. However, if the question wants us to make the observation that ##i## and ##j## are perpetually assigned 0, how would that affect your answer? I'm still unsure about how to answer the question...
##i## = ##i##++ increments the RHS ##i## after its assignment to the LHS ##i.## The correct syntax is either ##i =## ++##i## (increments before assignment), or just ++##i## or ##i##++. Source: http://stackoverflow.com/questions/24853/what-is-the-difference-between-i-and-i. ##i = i##++ assigns...
But notice that ##i## and ##j## are initialized as ##0## then 'updated' as follows: ##j = j * 2## and ##i = i##++. Therefore, their loops (the two outermost loops) would execute indefinitely. The innermost loop is the only one that properly increments its iteration counter. I'm wondering what...
Homework Statement
Consider the ##xyzzy## algorithm below. This algorithm takes a linear collection (e.g., a list or array) of size ##n## as an argument (i.e., as the input to the algorithm) and produces no return value (i.e., has no output, but might alter the linear collection). Note that the...
I meant ##c_2h < f## when ##g < f## after ##x = k_2## (which is the point at which ##g > c_2h##). Sorry, I'm just trying to visualize the graphs in my head and think about the theory. I'm not sure how to come up with a counterexample...
Hi haruspex, thanks for replying.
(a) What I meant to say was this:
##g## can be less than ##f.## Therefore, ##g##'s lower bound ##c_2h## must be less than ##f## over ##\forall x \geq k_2.## Therefore, with ##c = c_2## and ##k = k_2## as witnesses, it is not necessarily the case that ##f \in...
I must be missing something, but why wouldn't ##\forall x > k ~~~ f(x) > h(x)## mean ##f \notin O(h)##?
When I tried your suggested approach, this is what I got:
I'm given ##\forall x \geq k_2 ~~~ c_2h(x) \leq g(x),## so by dividing by ##c_2## I arrive at ##\forall x \geq k_2 ~~~ h(x) \leq...
Hi, thanks so much for replying! I'll try to explain my answer to (a) better. What I'm saying is:
##g## can be less than ##f## for ##\forall x \geq k,## in which case ##g##'s lower bound ##c_2h## must be less than ##f## for ##\forall x \geq k'.##
If ##c_2h < f## then ##f > h## for ##c_2 \geq...
Homework Statement
[/B]
Homework Equations
Provided in (1).
The Attempt at a Solution
I think (a) is no because, though ##c_1g > f,## the actual un-vertically-translated ##g## could be less than ##f,## meaning its lower bound ##c_2h < f## over ##c_2 \geq 1,## meaning ##h < f.## Am I...
The problem statements, all variables and given/known data:
Question 1
Question 2
Relevant equations: Provided in question snips.
The attempt at a solution:
Question 1: I think qux is the answer because it properly increments k by 1 in each iteration. j = j * 2 means j is always 0 so its...
Hi Stephen,
The next question in the assignment asks me to use a truth table, which should be easy enough. However, the preceding question asks for the use of logical equivalencies (reduction to T's and F's) to prove the original and derived expressions are logically equivalent. For this part...
Hi, thanks for taking the time to respond. Does this look correct to you?
Also, how would I prove that the original expression and the one I derived are equivalent using logical equivalencies? (I.e., I think I have to convert everything in the original and derived expressions to T's and F's...
Homework Statement
[/B]
Homework Equations
[/B]
The Attempt at a Solution
[/B]
And I just don't know what to do from here... Any help will be greatly appreciated!