Is Answer Wrong Or Is It A Bug?

Get Help Python
#1

Link To Exercise:
https://www.codecademy.com/courses/learn-data-structures-and-algorithms-with-python/quizzes/asymptotic-notation-conceptual-qz

Look at this picture:

image
image1920Ă—867 56.3 KB

It looks right, it says that O(N ^ 2) is less efficient than O(2^N) even though I put it in that order.

#2

You’re chosen the wrong order. 2^N should be after N^2

Let’s say N is 10. 10 squared is 100. 2 raised to the 10th power is 1024.

3 Likes
#3

Does that mean the O(2^N) is less efficient than O(N^2)? Then why did the explanation of the the wrong answer in the picture say the reverse:
O(N^2) is less efficient than O(2^N).

First, N = 1, 1 ^ 1 = 1, 2 ^ 1 = 2 More efficent: O(N ^ 2)
Second, N = 2, 2 ^ 2 = 4, 2 ^ 2 = 4, Same efficiency.
Not always, N = 3, 3 ^ 3 = 9, 2 ^ 3 = 8. More efficient: O(2 ^ N)
But this, N = 4, 4 ^ 2 = 16, 2 ^ 4 = 16. Same efficiency.
More, N = 5, 5 ^ 5 = 25, 2 ^ 5 = 32. More efficient: O(N ^ 2)
… (O(2 ^ N) getting more less efficient compared to O(N ^ 2). In fact first I didn’t think this and also thought O(N ^ 2) was more efficient than O(2 ^ N). I learnt something.
But I agree with you because normally big O uses huge inputs.

#4

That question will need to be reviewed. 2 ^ N is not quadratic. N ^ 2 is quadratic.

1 Like
#6

Your point is valid but you’ve got some incorrect equations written out.
N=1 should be 1^2, 2^1
N=3 should be 3^2, 2^3
N=5 should be 5^2, 2^5

Also when dealing with complexities you shouldn’t worry much about lower numbers, it’s meant to deal with very large numbers.

def expo_vs_quad(num): return [num, num**2, 2**num] for x in range(10,101, 10): print(expo_vs_quad(x))
1 Like
#7

I was thinking to use times instead of ^ instead of this:
First, N = 1, 1 ^ 1 = 1, 2 ^ 1 = 2 More efficient: O(N ^ 2)
Second, N = 2, 2 ^ 2 = 4, 2 ^ 2 = 4, Same efficiency.
Not always, N = 3, 3 ^ 3 = 9, 2 ^ 3 = 8. More efficient: O(2 ^ N)
But this, N = 4, 4 ^ 2 = 16, 2 ^ 4 = 16. Same efficiency.
More, N = 5, 5 ^ 5 = 25, 2 ^ 5 = 32. More efficient: O(N ^ 2)

I thought actually this:
First, N = 1, 1 x 1 = 1, 2 ^ 1 = 2 More efficient: O(N ^ 2)
Second, N = 2, 2 x 2 = 4, 2 ^ 2 = 4, Same efficiency.
Not always, N = 3, 3 x 3 = 9, 2 ^ 3 = 8. More efficient: O(2 ^ N)
But this, N = 4, 4 x 2 = 16, 2 ^ 4 = 16. Same efficiency.
More, N = 5, 5 x 5 = 25, 2 ^ 5 = 32. More efficient: O(N ^ 2)
.

But I should write it as squared like this:

.

With all the extra comparison notes at the end and also, N = 2, N = 4.

Yes I new that before as in this quote from me:

.