- #1
GeorgeCostanz
- 31
- 0
I'm trying to grasp some basic concepts of analyzing code segments. Not sure if I have the right thought process. Can't find many examples online.
A.)
for (i=1; i<n; i++)
for (j=1; j<n; j++)
return 1
Guess: Theta(n) because both loops go to (n) and they're independent? or is it constant because it's only doing a constant bit of work?
B.)
for (i=1; i<n; i++)
for (j=1; j<log n; j++)
A[j] = 3A[j]
Guess: Theta(n) because the outer loop goes to (n)?
C.)
for (i=1; i<5; i++)
for (j=1; j<i; j++)
A[j] = 0
Guess: Theta(1) because it executes in constant time?
D.)
for (i=1; i<5; i++)
for (j=1; j<i; j++)
i = n
Guess: Theta(1) because it executes in constant time?
E.)
x = n
while (x > 1)
x = x/2
Not sure how to do this
F.)
x = 1
while (x<n)
x = x+3
Not sure how to do this either.
3. The Attempt at a Solution [/B]
I put the attempts in part 1 because it's easier to follow. Any help would be appreciated, thanks.
Homework Statement
A.)
for (i=1; i<n; i++)
for (j=1; j<n; j++)
return 1
Guess: Theta(n) because both loops go to (n) and they're independent? or is it constant because it's only doing a constant bit of work?
B.)
for (i=1; i<n; i++)
for (j=1; j<log n; j++)
A[j] = 3A[j]
Guess: Theta(n) because the outer loop goes to (n)?
C.)
for (i=1; i<5; i++)
for (j=1; j<i; j++)
A[j] = 0
Guess: Theta(1) because it executes in constant time?
D.)
for (i=1; i<5; i++)
for (j=1; j<i; j++)
i = n
Guess: Theta(1) because it executes in constant time?
E.)
x = n
while (x > 1)
x = x/2
Not sure how to do this
F.)
x = 1
while (x<n)
x = x+3
Not sure how to do this either.
Homework Equations
3. The Attempt at a Solution [/B]
I put the attempts in part 1 because it's easier to follow. Any help would be appreciated, thanks.