• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Tim Cooke
  • Jeanne Boyarsky
  • Liutauras Vilda
Sheriffs:
  • Frank Carver
  • Henry Wong
  • Ron McLeod
Saloon Keepers:
  • Tim Moores
  • Frits Walraven
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Himai Minh

Algorithm Analysis

 
Ranch Hand
Posts: 373
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I got this question wrong on my test and I want to know why.
quiz.jpg
[Thumbnail for quiz.jpg]
 
Marshal
Posts: 8412
606
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So, you have a task to move 3 numbers to the back of an array.

Let's forget that for a moment.

Let's assume you need to take very first number and move it to the end of an array. What the time complexity would be? O(n). Why? That's because you'd need (going to say in simpler words, but not quite exactly what's happening) to take very first value and going step by step starting from the start position to a finish line. Meaning you'd need to go all the distance (array's length) once.

And so think of it you have done it in 5 seconds. So you ran through the distance of n in 5 seconds.

Now, the description says how the algorithm is implemented, "that you take one value at a time...".

So having said that, after you moved 1 element to an end of an array, you need to do the same now with the other first element (it was second in initial setup) - so it takes yet again 5 seconds.

Finally you need to take another first element and move it to the end - yet again 5 seconds.

So you moved 3 elements. m = 3, and n = 5s.

so O(m*n) = 15 s, makes sense, right?


It would be O(n) if you could take all 3 elements at once (check once again in instructions what is said about the used algorithm) and carry them over to the end of an array.
 
Liutauras Vilda
Marshal
Posts: 8412
606
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I just probably used N and M interchanged, so really according to an instructions M represents values in an array, while N represents a number of elements to move. I used them otherway round - but that doesn't change the answer, idea is the same.
 
Ana Smith
Ranch Hand
Posts: 373
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Why is this statement true?
bigo.jpg
[Thumbnail for bigo.jpg]
 
Marshal
Posts: 76440
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Why have you got log₁₀₀ in one place and log₂ in the other?
 
Saloon Keeper
Posts: 14289
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Campbell, that's just the exam question and not a bad one at that. It illustrates that the base of the logarithm doesn't matter.

Ana, do you know what exactly O(log n) means?
 
Campbell Ritchie
Marshal
Posts: 76440
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That's what I thought. But in that case surely the time complexity would be logN with the base omitted. After all, logs increase the same way irrespective of their base.
 
Stephan van Hulst
Saloon Keeper
Posts: 14289
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It doesn't matter. The argument to the O function may be any function. O(log₂ n) and O(log₁₀₀ n) return the same set. It's convention to write complexity classes using the simplest form, but it's not technically incorrect to pass in more information than needed.
 
Campbell Ritchie
Marshal
Posts: 76440
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sounds as though we are both thinking the same wway and expressing it differently. Agreed that you can have any base or no base for the log and it is still correct.
 
Ana Smith
Ranch Hand
Posts: 373
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Campbell, that's just the exam question and not a bad one at that. It illustrates that the base of the logarithm doesn't matter.

Ana, do you know what exactly O(log n) means?


I know that it means log base 2 n.
 
Campbell Ritchie
Marshal
Posts: 76440
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ana Smith wrote:

Stephan van Hulst wrote:. . . the base of the logarithm doesn't matter.

Ana, do you know what exactly O(log n) means?


I know that it means log base 2 n.

I think you have completely missed the whole point of this discussion.
 
Stephan van Hulst
Saloon Keeper
Posts: 14289
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Let me rephrase. What does O(n) stand for, what concept does it represent?
 
Liutauras Vilda
Marshal
Posts: 8412
606
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@OP

Log2(n) - let's multiply its base few times 2 x 2 x 2 = 8, and so if we had Log2(8) what the answer would be?

Log100(n) - let's multiply again its base few times 100 x 100 x 100 = 1000000, and so if we had Log100(1000000) what the answer would be?
 
Liutauras Vilda
Marshal
Posts: 8412
606
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Maybe reminding yourself some definition would help to derive to some conclusion.

"The runtime O(f(n)) means that with the growth of n the runtime of the program grows proportionally to fuction f(n)."

Now in a case of Log2(8) and Log100(1000000), we increased n significantly, but how the answer differed?

Answer questions in the post above and you'll know the answer.
 
Campbell Ritchie
Marshal
Posts: 76440
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Also go back to your older thread; in the case of nlogn complexity, I had a little formula. If you go and change the two instances of log there to log₂ or log₁₀₀ or some other base, and see what the result comes to. You can simplify that formula a bit to match logn time complexity
 
Bartender
Posts: 5064
188
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And yet another clue:

remember the formula from school:  Log_a(b) = Log_c(b) / Log_c(a), so Log_a(b) and Log_c(b) differ by a constant factor. See the def of Big_O what that means for O(Log_a) and O(Log_c)
 
Sheriff
Posts: 17120
298
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think in this case it might be helpful to give OP a more direct answer.

The statement in question is true because Big O is about the shape of the curve. That means you can ignore things like constants, e.g., the base of the log.

See this: https://stackoverflow.com/questions/20512642/big-o-confusion-log2n-vs-log3n/20512708#20512708
 
I'm a lumberjack and I'm okay, I sleep all night and work all day. Lumberjack ad:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic