Question

Having a little trouble with the Big Oh Notation. I understand the concept but not the calculations. I tried an easier one... is it right? Not just the answer... but the algorithm.

http://dpaste.com/563543/

Answer 1

http://dpaste.com/563546/

that's another one... quad

Answer 2

Not sure what you are asking, Big O is kinda a concept. It is an asymptotic notation. Big O describes the upper bound or limit - the worst case. There isn't an algorithm for this but the 'complexity' of an algorithm can be described by Big O.

You did get the correct complexity for the two functions you posted

Answer 3

Ok good. i do pretty much understand the concept, perhaps that's all I need to know at this point. Just that I couldn't quite follow the lecture when he was talking about the algorithms he used to get to the Big O type.
I get that binary is log, step-by-step is linear, multiple recursion calls is exponential... hopefuly that is enough for now.

Just a bit worried that I'll make mistakes if I can't do the algorithms.

Answer 4

if there is anything i learned from everyone saying "i don't understand big O notation" its that few people understand it, and that fewer people need to know what it means.

your line "I get that binary is log, step-by-step is linear, multiple recursion calls is exponential... hopefuly that is enough for now." is about as much as i know, basically learn what makes a program slow, they'll teach you ways to get around it later.

I'm fairly confident that big O notation is only taught to you so the next few lectures about optimization are easier to understand, as far as I remember you never use it in the course and I doubt you'd use it outside a formal setting like optimizing googles searches, or in writing research papers about programming.

Answer 5

also is it just me or are more and more people asking questions that are less and less relivant to this course popping up on this board?

Answer 6

okay good I'm satisfied then.

Haha yeah some people get lost and end up in the wrong place lol.

Answer 7

This is an 'intro' class so supposedly it is an introduction to some fundamentals of computer science as well as programming.

Lotsa hits for a Big O search, it may be a commonplace term or concept in certain fields. I only skimmed this but maybe it will help:
http://www.perlmonks.org/?node_id=573138

Answer 8

Thanks! :)