The Big O

[newbiec++]

Question on the Big-O runtime efficiency
Need some help with these problems


Assume T(n) is a count of the number of key operations for an algorithm that processes a list of n elements. Determine the Big-O runtime efficiency of the algorithm.

T(n) = O(1) is there an answer for this?? nothing to solve?

T(n) = O(n) is there an answer for this?? nothing to solve?

Indicate the running time of each algorithm or code segment.

Outputting the first and last letter in a string: (i) O(n2), (ii) O(n), (iii) O(1), (iv) O(log2 n)?

Determining the number of tokens (blocks of nonwhitespace characters) in a string: (i) O(n2), (ii) O(n), (iii) O(1), (iv) O(log2 n) ?

[Rashakil Fol]

This would depend on what the definition of 'string' is.

[edit]Oh, and what do you expect as a response? You haven't explained what you don't understand.

[IfYouSaySo]

This would depend on what the definition of 'string' is.

I was thinking the same thing, but I couldn't think of a clever enough way to say it. There are at least 3 different types of strings I can think of: std::string, c style strings, and length prefixed strings. I bet his professor was talking about std::string, so the answer is O(1). I can't wait for someone to scream, "That's not true--it's implementation dependent!"

[VirtualAce]

I thought this thread was about something totally different based on the title, but I guess that discussion would be reserved for another forum.