• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 16:13
CET 22:13
KST 06:13
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Team Liquid Map Contest #2312[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11
Community News
Weekly Cups (Nov 9-15): Clem and herO take over6Dark completes military service, returns to SC217[BSL23] RO16 Group Stage20Weekly Cups (Nov 2-8): herO back on top?2Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0
StarCraft 2
General
Weekly Cups (Nov 9-15): Clem and herO take over SC4ALL: II Indiegogo Campaign Announcement No more SC2 streamers on team liquid? Team Liquid Map Contest #23 StarCraft open world shooter announced at BlizzCon
Tourneys
RSL goes to London! 2026 Offline Finals Nov 21-22 soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16) Sparkling Tuna Cup - Weekly Open Tournament Sea Duckling Open (Global, Bronze-Diamond) Dark returns! GSL CK #7 4v4 Team Battle (Nov 19)
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps Starcraft 2 Advance [D] the control group Simple Questions/Answers
External Content
Mutation # 553 Undermined The PondCast: SC2 News & Results Mutation # 552 Secret Storm Mutation # 551 Robotic Revival
Brood War
General
People still play BW? List of top players active on ShieldBattery SC4ALL: II Indiegogo Campaign Announcement XUN appreciation thread BW General Discussion
Tourneys
$3,000 Sijosae Tier 2,3,4 Cup (Nov 23-24 2026) [BSL23] Ro16 Group B - Saturday 21:00 CET 2v2v2v2 Tournament Stage 2: Players KCM Race Survival 2026 Season 4
Strategy
Pluto's TvP 5Marine 2Medic Push Simple Questions, Simple Answers Infested Terran strategies in 2026 Nuke strategy worked in K-League 2026-11-09
Other Games
General Games
Nintendo Switch Thread The PlayStation 5 Stormgate/Frost Giant Megathread Warcraft III: The Frozen Throne Free Space RTS Game, optimised f. Phone/Tablet etc
Dota 2
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
US Politics Mega-thread The Games Industry And ATVI Russo-Ukrainian War Thread Things Aren’t Peaceful in Palestine Trading/Investing Thread
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
Formula 1 Discussion Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
The time I organised my…
AssyrianKing
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
Can Bots Beat Pros?? Starcr…
namkraft
James Bond movies ranking - pa…
Topin
StarCraft improvement
iopq
Socialism Anyone?
GreenHorizons
Customize Sidebar...

Website Feedback

Closed Threads



Active: 18779 users

The Big Programming Thread - Page 788

Forum Index > General Forum
Post a Reply
Prev 1 786 787 788 789 790 1032 Next
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks.
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2016-10-29 23:58:13
October 29 2016 23:52 GMT
#15741
On October 29 2016 06:47 centirius wrote:
C# solution (so probably works in Java with minimal changes I suppose) also O(n^2) obv


bool HasTwoSubArraysWithSameTotal(int[] values){
return HasTwoSubArraysWithSameTotal(values, 0, 0, 0);
}

bool HasTwoSubArraysWithSameTotal(int[] values, int sumA, int sumB, int index){
return values.Length == index ? sumA == sumB :
HasTwoSubArraysWithSameTotal(values, sumA + values[index], sumB, index + 1) ||
HasTwoSubArraysWithSameTotal(values, sumA, sumB + values[index], index + 1);
}



Good catch that this can be done without storing the actual arrays, I didn't catch that.
There is no one like you in the universe.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
October 30 2016 18:31 GMT
#15742
Some review questions, testing my knowledge of big-O notation

20. True/False ‘
a. 7n^2+10n+100 is O(1) False
b. 7n^2+10n+100 is O(n) False
c. 7n^2+10n+100 is O(n^2) True
d. 7n^2+10n+100 is O(n^3) True
e. 7n^2+10n+100 is O(2^n) True
21. True/False
a. 7n^2+10n+100 is θ(1) False
b. 7n^2+10n+100 is θ (n) False
c. 7n^2+10n+100 is θ (n^2) True
d. 7n^2+10n+100 is θ (n^3) False
e. 7n^2+10n+100 is θ (2^n) False

Is my understanding correct?

and then little o notation .. if my understanding of the above is correct could someone explain little-o to me?
phar
Profile Joined August 2011
United States1080 Posts
Last Edited: 2016-10-30 18:39:08
October 30 2016 18:36 GMT
#15743
Yes you're correct. You already got that O is upper bound, and theta is both upper and lower bound. o is just lower bound.

So n^2 + n + 5 is

O(n^2), O(n^3), O(n^5), etc...

o(n^2), o(n), o(nlog(n)), o(1), etc...

Same idea, just on the other side.



In practice in industry all that gets talked about is theta, but confusingly they will call it O when then mean theta. But you can worry about that later.
Who after all is today speaking about the destruction of the Armenians?
phar
Profile Joined August 2011
United States1080 Posts
October 30 2016 18:37 GMT
#15744
Or for your abcde question there,

O is FFTTT
Theta is FFTFF
o is TTTFF
Who after all is today speaking about the destruction of the Armenians?
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
October 30 2016 18:48 GMT
#15745
Okay cool

Followup question about big o, this time actually looking at a couple situations and determining the complexity


a. for (int i = 0; i < n; i++) {
for (int j = n; j >= i; j++) { … } }


outside goes through n times, inside ends up going through..... just throwing out an observation... 2^(n-1) ?
is this O(2^(n-1)) ?


b. for (int i = 10000; i < 50000; i++) {
for (int j = n; j >= 1; j /= 2) { … } }


outside goes through constant times
inside goes through... uh.. it looks like it keeps dividing by 2. So that's log(n) ? This one is a lot weirder to me
Is the answer O(log(n)) ?
RoomOfMush
Profile Joined March 2015
1296 Posts
October 30 2016 19:02 GMT
#15746
On October 31 2016 03:48 travis wrote:

a. for (int i = 0; i < n; i++) {
for (int j = n; j >= i; j++) { … } }


outside goes through n times, inside ends up going through..... just throwing out an observation... 2^(n-1) ?
is this O(2^(n-1)) ?

This one is not only tricky, its immensely stupid. Please never ever code like this. Everybody will believe you made a mistake when you write code like that. The example doesnt even make sense with the big-O-notation. The number of iterations is not really limited by the input but by the size of integers on your execution enviroment. In java that is 32bit integers and thus (2^31)-1 positive values.
If we go with the most rigorous interpretation of the big-O-notation the loop over the variable j would be constant and thus O(1). If we use that interpretation though the loop over the variable i would also be O(1) because (2^31)-1 is also an upper bound for n. Since n must be less than 2^31 => O(n) == O(2^31) == O(1) but you can apply this logic to every algorithm in java. This makes the entire exercise pointless.
Whoever came up with that question is either stupid or expects you to realize on your own that the exercise is stupid.
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
October 30 2016 19:11 GMT
#15747
^ lol I thought I misread it but it is as stupid as it seems...
maybe travis meant j-- in which it'd O(n^3)
There is no one like you in the universe.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
October 30 2016 19:22 GMT
#15748
Well, I think the only point is to test your ability to figure out the complexity. I didn't write it, the professor did.

I get what you are saying, mush, but I feel like what you are saying is a little pointless.
spinesheath
Profile Blog Joined June 2009
Germany8679 Posts
Last Edited: 2016-10-30 20:07:22
October 30 2016 19:55 GMT
#15749
On October 31 2016 03:48 travis wrote:

b. for (int i = 10000; i < 50000; i++) {
for (int j = n; j >= 1; j /= 2) { … } }


outside goes through constant times
inside goes through... uh.. it looks like it keeps dividing by 2. So that's log(n) ? This one is a lot weirder to me
Is the answer O(log(n)) ?

The outer loop does nothing to change the complexity, it just applies a constant factor of 40000 which is irrelevant for big O.

For the inner loop, imagine it was j /= 10: in this case it would run as many times as n has digits in the decimal system - each division cuts off the last digit. The number of digits is log_10(n) (logarithm with base 10). So this would be O(log_10(n)). In the actual example the same reasoning works if you think of n as a binary number, so it runs in O(log_2(n)).

You write log(n), which usually is interpreted as log_10(n). But whether you meant base 10 or 2 or e, O(log(n)) is right anyways because log_b(n) = C * log_a(n), where C = log_b(a) is a constant.


For question a, please double check that you didn't make a mistake when copying it. If that is the exact version, we have to assume that the inner loop is either constant (Integer.MaxValue + 1 overflows into a negative value) or infinite if you don't restrict the range. So the whole thing would either be O(n) or infinite. It really is stupid though.
And it certainly is not anything like O(2^n). It's either O(1), O(n). O(n^2) or infinite. For a function f(n) you usually get 2^n stuff if you recursively do 2 calls to f(n - 1), n levels of recursion deep. Not if you nest two loops like that.
If you have a good reason to disagree with the above, please tell me. Thank you.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
October 30 2016 20:17 GMT
#15750
oh i see, i did misread it.
but yeah that's what the professor wrote, i copy pasted it.

I see what you guys are saying, inner loop goes forever

sorry about that mush
RoomOfMush
Profile Joined March 2015
1296 Posts
Last Edited: 2016-10-30 20:43:52
October 30 2016 20:43 GMT
#15751
On October 31 2016 05:17 travis wrote:
oh i see, i did misread it.
but yeah that's what the professor wrote, i copy pasted it.

I see what you guys are saying, inner loop goes forever

sorry about that mush

Its worse than "inner loop goes forever".
In every actual programming language the loop will not go forever. The range of integer variables is limited and thus it will end fairly quickly. The problem with that is that the big-O-notation doesnt work for actual real-life examples. Its a purely theoretical construct which can only be used in a gedankenexperiment. Once you try to use it on real-world code you will get O(1) for most pieces of code like the ones you posted.

If we, on the other hand, assume that your code is pseudo-code and has nothing to do with real life then the answer is that it runs forever. In this case we can not give an upper bound and there is nothing in the big-O notation that you can write to express that.

The example simply doesnt make any sense at all no matter how you look at it.
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
October 30 2016 20:55 GMT
#15752
I'd just ask the professor to clarify that question, I can't imagine that it's not j-- unless the professor wanted you to think super outside the box or something like that.
There is no one like you in the universe.
raNazUra
Profile Joined December 2012
United States10 Posts
October 30 2016 21:37 GMT
#15753
On October 31 2016 03:36 phar wrote:
Yes you're correct. You already got that O is upper bound, and theta is both upper and lower bound. o is just lower bound.

So n^2 + n + 5 is

O(n^2), O(n^3), O(n^5), etc...

o(n^2), o(n), o(nlog(n)), o(1), etc...

Same idea, just on the other side.



In practice in industry all that gets talked about is theta, but confusingly they will call it O when then mean theta. But you can worry about that later.


This is incorrect. Omega is the lower-bound analysis, not little-o. Little-o is the same as big O, but it is strictly greater. If an algorithm is O(f(n)), but not Theta(f(n)) (that is, the bound is not tight), then it is o(f(n)). It's like the difference between <= and <.
Speak the truth, even if your voice shakes
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
October 31 2016 01:30 GMT
#15754
okay, professor got back to me. it was supposed to be j--

so outside goes through n times
so inside goes through... I have no idea
how do I figure this out
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2016-10-31 02:21:22
October 31 2016 02:16 GMT
#15755
:p

when you have problems like this, i think it helps to manually count.

so for the inside loop, can you manually count the number of iterations?

at i = 0, j = n, j >= i, j-- will loop... n times
at i = 1, j = n, j >= i, j-- will loop... ? times
at i = ...
at i = n-1, j = n, j >= i, j-- will loop... ? times

that should get you started
There is no one like you in the universe.
phar
Profile Joined August 2011
United States1080 Posts
October 31 2016 07:42 GMT
#15756
On October 31 2016 06:37 raNazUra wrote:
Show nested quote +
On October 31 2016 03:36 phar wrote:
Yes you're correct. You already got that O is upper bound, and theta is both upper and lower bound. o is just lower bound.

So n^2 + n + 5 is

O(n^2), O(n^3), O(n^5), etc...

o(n^2), o(n), o(nlog(n)), o(1), etc...

Same idea, just on the other side.



In practice in industry all that gets talked about is theta, but confusingly they will call it O when then mean theta. But you can worry about that later.


This is incorrect. Omega is the lower-bound analysis, not little-o. Little-o is the same as big O, but it is strictly greater. If an algorithm is O(f(n)), but not Theta(f(n)) (that is, the bound is not tight), then it is o(f(n)). It's like the difference between <= and <.


Ah yea, you're right, I had completely forgotten about Ω. In part, cus as previously mentioned, industry tends to be a bit... cavalier with definitions.
Who after all is today speaking about the destruction of the Armenians?
mantequilla
Profile Blog Joined June 2012
Turkey781 Posts
October 31 2016 10:49 GMT
#15757
http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html

why are there always last two versions of jdk on the download page? the latest one below and the older one on top? why would I want to download not the latest one but just 1 before the latest?
Age of Mythology forever!
Djagulingu
Profile Blog Joined December 2010
Germany3605 Posts
October 31 2016 11:13 GMT
#15758
On October 31 2016 19:49 mantequilla wrote:
http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html

why are there always last two versions of jdk on the download page? the latest one below and the older one on top? why would I want to download not the latest one but just 1 before the latest?


Because:

On October 28 2016 02:44 Nesserev wrote:
Show nested quote +
On October 27 2016 22:04 Djagulingu wrote:
Fuck Oracle

ftfy, efficiency matters

"windows bash is a steaming heap of shit" tofucake
RoomOfMush
Profile Joined March 2015
1296 Posts
October 31 2016 16:11 GMT
#15759
On October 31 2016 19:49 mantequilla wrote:
http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html

why are there always last two versions of jdk on the download page? the latest one below and the older one on top? why would I want to download not the latest one but just 1 before the latest?

Probably in case the latest one has bugs. Instead of waiting for a hotfix you can downgrade and perhaps things will work out that way.
mantequilla
Profile Blog Joined June 2012
Turkey781 Posts
Last Edited: 2016-10-31 17:20:37
October 31 2016 17:19 GMT
#15760
I guessed like that too. It indicates latest version usually ( ) has bugs since older one is on the top. They want you to download the older one. Or they expect you to usually download it. Or all this is wrong and there's a more technically correct answer.

since bosses are reluctant to even use java 7 (not yet mature ), it's a funny thing.
Age of Mythology forever!
Prev 1 786 787 788 789 790 1032 Next
Please log in or register to reply.
Live Events Refresh
BSL
05:00
S23 - Ro16 Group D
Bonyth vs Doodle
Kyrie vs Jimin
ZZZero.O276
LiquipediaDiscussion
IPSL
02:00
Ro16 Group A
Ret vs ggnore13
nOmaD vs Aether
Liquipedia
RSL Revival
22:00
Offline Finals: Playoffs
Serral vs herOLIVE!
Tasteless3102
ComeBackTV 1355
RotterdaM1315
IntoTheiNu 663
TaKeTV 601
IndyStarCraft 396
kabyraGe 239
LamboSC2232
Rex66
3DClanTV 54
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Tasteless 3102
RotterdaM 1315
IndyStarCraft 396
LamboSC2 232
ProTech142
Rex 66
JuggernautJason37
EmSc Tv 9
StarCraft: Brood War
Britney 19554
Shuttle 318
ZZZero.O 276
Noble 7
Dota 2
Gorgc8378
Counter-Strike
pashabiceps1869
gobbtv115
Super Smash Bros
Mew2King53
Heroes of the Storm
Liquid`Hasu507
Khaldor273
Other Games
tarik_tv4158
Grubby2889
FrodaN1332
B2W.Neo671
ToD172
Pyrionflax140
Organizations
Other Games
gamesdonequick1135
StarCraft 2
EmSc Tv 9
[ Show 14 non-featured ]
StarCraft 2
• Adnapsc2 20
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• 80smullet 17
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Other Games
• imaqtpie905
• Shiphtur399
• Scarra230
• tFFMrPink 13
Upcoming Events
Replay Cast
1h 47m
Tournament
10h 47m
WardiTV Weekly
14h 47m
Ultimate Battle
14h 47m
Bisu vs Light
Kung Fu Cup
1d 13h
Solar vs Classic
ByuN vs SHIN
PiGosaur Cup
2 days
The PondCast
3 days
KCM Race Survival
3 days
Liquipedia Results

Completed

Proleague 2026-11-17
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
BSL Season 23
IPSL Winter 2026-27
RSL Offline Finals
Calamity Cup Div. A Season 8
Underdog Cup 2026 Div 2-3
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3

Upcoming

CSL Season 23: Qualifier 1
Sector 591
Sijosae Cup
CSL Season 23: Qualifier 2
YSL S4
SC4ALL II: Brood War
CSL 2026 Winter (S23) - 3v3
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
IEM Kraków 2027
PGL Bucharest 2027
BLAST Bounty Winter 2027
PGL Major Singapore 2026
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.