This forum is now read-only. Please use our new forums! Go to forums

0 points
Submitted by David Laing
over 11 years

3.2 Maximum Element

This exercise is proving quite confusing. I still have only a foggy grasp of what “Big O” actually is. How do I find what the “Big O” is for this exercise?

Answer 50d43393d4bcb2de04001cc9

4 votes
Best answer

Permalink

Think visually. This idea may make it simple as well:

  1. let’s generalise the case for 3 arrays of length n:

palt textp

  1. start with the simplest case:

palt textp

  1. Now do the same thing with two arrays:

alt text

  1. Links to images (because they get cropped here): http://i.imgur.com/0HhZc.png http://i.imgur.com/4ToNF.png http://i.imgur.com/JLLqh.png
points
Submitted by Aleksandrs Čudars
over 11 years

2 comments

Jacob Andersen almost 11 years

Wow. Very nice, mate!

Raymond Dipasupil almost 11 years

this is really really helpful!

Answer 4ff72596a1a6800003035c42

5 votes

Permalink

OK, have managed to stumble upon the answer having looked up a couple of Youtube videos and looked on Stackoverflow. The answer is O(n^2). Both this video (http://www.youtube.com/watch?v=6Ol2JbwoJp0) and this forum (http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it#_=_) were helpful in developing my understanding.

points
Submitted by David Laing
over 11 years

Answer 50ea7d1458ee6774ba0053b4

1 vote

Permalink

It’s two times nested, so you have a n^2 notation. i.e.O(n^2)

points
Submitted by Roeland
about 11 years

1 comments

Sofia Perwallius almost 10 years

Thanks