« previous next »
Pages: [1]   Go Down

Author Topic: Should string comparisons and other operations be considered O(1) or O(n)?  (Read 3905 times)

0 Members and 1 Guest are viewing this topic.

Offline blue_bear_94

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 801
  • Rating: +25/-35
  • Touhou Enthusiast / Former Troll / 68k Programmer
    • View Profile
Should string comparisons and other operations be considered O(1) or O(n)?
« 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.
Logged
Due to dissatisfaction, I will be inactive on Omnimaga until further notice. (?? THP hasn't been much success and there's also the CE. I might possibly be here for a while.)
If you want to implore me to come back, or otherwise contact me, I can be found on GitHub (bluebear94), Twitter (@melranosF_), Reddit (/u/Fluffy8x), or e-mail (if you know my address). As a last resort, send me a PM on Cemetech (bluebear94) or join Touhou Prono (don't be fooled by the name). I've also enabled notifications for PMs on Omnimaga, but I don't advise using that since I might be banned.
Elvyna (Sunrise) 4 5%
TI-84+SE User (2.30 2.55 MP 2.43)
TI-89 Titanium User (3.10)
Casio Prizm User? (1.02)
Bag  東方ぷろの

Offline willrandship

  • Omnimagus of the Multi-Base.
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2953
  • Rating: +98/-13
  • Insert sugar to begin programming subroutine.
    • View Profile
Re: Should string comparisons and other operations be considered O(1) or O(n)?
« Reply #1 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.
Logged

Offline blue_bear_94

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 801
  • Rating: +25/-35
  • Touhou Enthusiast / Former Troll / 68k Programmer
    • View Profile
Re: Should string comparisons and other operations be considered O(1) or O(n)?
« Reply #2 on: October 28, 2013, 05:31:27 pm »
I meant with the default comparison operator.
Logged
Due to dissatisfaction, I will be inactive on Omnimaga until further notice. (?? THP hasn't been much success and there's also the CE. I might possibly be here for a while.)
If you want to implore me to come back, or otherwise contact me, I can be found on GitHub (bluebear94), Twitter (@melranosF_), Reddit (/u/Fluffy8x), or e-mail (if you know my address). As a last resort, send me a PM on Cemetech (bluebear94) or join Touhou Prono (don't be fooled by the name). I've also enabled notifications for PMs on Omnimaga, but I don't advise using that since I might be banned.
Elvyna (Sunrise) 4 5%
TI-84+SE User (2.30 2.55 MP 2.43)
TI-89 Titanium User (3.10)
Casio Prizm User? (1.02)
Bag  東方ぷろの

Offline willrandship

  • Omnimagus of the Multi-Base.
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2953
  • Rating: +98/-13
  • Insert sugar to begin programming subroutine.
    • View Profile
Re: Should string comparisons and other operations be considered O(1) or O(n)?
« Reply #3 on: October 28, 2013, 05:32:07 pm »
That implementation varies between compilers and between architectures.

Oh wait, TI-BASIC sub
« Last Edit: October 28, 2013, 05:32:27 pm by willrandship »
Logged

Offline blue_bear_94

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 801
  • Rating: +25/-35
  • Touhou Enthusiast / Former Troll / 68k Programmer
    • View Profile
Re: Should string comparisons and other operations be considered O(1) or O(n)?
« Reply #4 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.
Logged
Due to dissatisfaction, I will be inactive on Omnimaga until further notice. (?? THP hasn't been much success and there's also the CE. I might possibly be here for a while.)
If you want to implore me to come back, or otherwise contact me, I can be found on GitHub (bluebear94), Twitter (@melranosF_), Reddit (/u/Fluffy8x), or e-mail (if you know my address). As a last resort, send me a PM on Cemetech (bluebear94) or join Touhou Prono (don't be fooled by the name). I've also enabled notifications for PMs on Omnimaga, but I don't advise using that since I might be banned.
Elvyna (Sunrise) 4 5%
TI-84+SE User (2.30 2.55 MP 2.43)
TI-89 Titanium User (3.10)
Casio Prizm User? (1.02)
Bag  東方ぷろの

Offline willrandship

  • Omnimagus of the Multi-Base.
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2953
  • Rating: +98/-13
  • Insert sugar to begin programming subroutine.
    • View Profile
Re: Should string comparisons and other operations be considered O(1) or O(n)?
« Reply #5 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.
Logged

Offline blue_bear_94

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 801
  • Rating: +25/-35
  • Touhou Enthusiast / Former Troll / 68k Programmer
    • View Profile
Re: Should string comparisons and other operations be considered O(1) or O(n)?
« Reply #6 on: October 28, 2013, 05:42:04 pm »
I'm writing a TI-Basic book.
Logged
Due to dissatisfaction, I will be inactive on Omnimaga until further notice. (?? THP hasn't been much success and there's also the CE. I might possibly be here for a while.)
If you want to implore me to come back, or otherwise contact me, I can be found on GitHub (bluebear94), Twitter (@melranosF_), Reddit (/u/Fluffy8x), or e-mail (if you know my address). As a last resort, send me a PM on Cemetech (bluebear94) or join Touhou Prono (don't be fooled by the name). I've also enabled notifications for PMs on Omnimaga, but I don't advise using that since I might be banned.
Elvyna (Sunrise) 4 5%
TI-84+SE User (2.30 2.55 MP 2.43)
TI-89 Titanium User (3.10)
Casio Prizm User? (1.02)
Bag  東方ぷろの

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Should string comparisons and other operations be considered O(1) or O(n)?
« Reply #7 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)
Logged
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline willrandship

  • Omnimagus of the Multi-Base.
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2953
  • Rating: +98/-13
  • Insert sugar to begin programming subroutine.
    • View Profile
Re: Should string comparisons and other operations be considered O(1) or O(n)?
« Reply #8 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.
Logged
Pages: [1]   Go Up
« previous next »