Omnimaga

Calculator Community => TI Calculators => TI-BASIC => Topic started by: blue_bear_94 on October 28, 2013, 05:29:58 pm

Title: Should string comparisons and other operations be considered O(1) or O(n)?
Post by: blue_bear_94 on October 28, 2013, 05:29:58 pm

In your opinion, should string comparisons be treated as O(1) (constant-time) or O(n) (linear time)? Technically testing for equality should consist of comparing each character, so it should be linear-time, but doing so is fast compared to interpreting the "=" operator.

Title: Re: Should string comparisons and other operations be considered O(1) or O(n)?
Post by: willrandship on October 28, 2013, 05:31:02 pm

That depends on your implementation of string comparison. The complexity is based on actual runtime.

If you have some fancy hardware hasher or comparison generator, then it would be O(1), but it's O(n) most of the time.

Title: Re: Should string comparisons and other operations be considered O(1) or O(n)?
Post by: blue_bear_94 on October 28, 2013, 05:31:27 pm

I meant with the default comparison operator.

Title: Re: Should string comparisons and other operations be considered O(1) or O(n)?
Post by: willrandship on October 28, 2013, 05:32:07 pm

That implementation varies between compilers and between architectures.

Oh wait, TI-BASIC sub

Title: Re: Should string comparisons and other operations be considered O(1) or O(n)?
Post by: blue_bear_94 on October 28, 2013, 05:40:02 pm

Hmm... in the worst case, comparing both 1-character strings and 999-character strings takes less than 20 ms.

Title: Re: Should string comparisons and other operations be considered O(1) or O(n)?
Post by: willrandship on October 28, 2013, 05:41:08 pm

Why are we talking about complexity in TI-BASIC? This is a case where actual runtime speed makes far more difference than complexity. I would take an n^2 algo that is twice as fast for low n over an n log n.

Title: Re: Should string comparisons and other operations be considered O(1) or O(n)?
Post by: blue_bear_94 on October 28, 2013, 05:42:04 pm

I'm writing a TI-Basic book.

Title: Re: Should string comparisons and other operations be considered O(1) or O(n)?
Post by: AngelFish on October 28, 2013, 06:35:47 pm

Quote from: blue_bear_94 on October 28, 2013, 05:29:58 pm

Technically testing for equality should consist of comparing each character, so it should be linear-time, but doing so is fast compared to interpreting the "=" operator.

Time complexity has nothing to do with how "fast" or "slow" a particular implementation is. It's how quickly a problem scales with the size of the input. Since strings have to be read character by character and the length of a string in characters is O(n), then the time complexity to compare two strings is equivalent to reading two strings, assuming character comparison is O(1). Thus, we have strcmp() = O(n)+O(n) = O(n)

Title: Re: Should string comparisons and other operations be considered O(1) or O(n)?
Post by: willrandship on October 28, 2013, 06:37:00 pm

^ this for TI-BASIC in particular. No way does the z80 have any fancy string comparison stuff in its hardware.