Big O Notation Help | Code Society | Page 1

loud scroll Sep 27, 2023, 11:16 PM

#

I am unsure of how to go about solving this. Obviously lines 1-5 are just O(n), but for 6-12, I am not sure if it is O(log(n))? I am supposed to find the algorithm's final Big O Notation, but this is admittedly more difficult with pseudocode than I had anticipated. Would anyone mind walking me through the logic?

worldly quest Sep 28, 2023, 12:11 AM

#

why would you say O(log(n)) and not O(n^2)?
First thing that come to my mind when I skim thorough this is that I see two nested loop (nested loop mean something time something thus n*n thus** n^2** thus O(n^2).

#

Does not mean your algo is O(n^2), but this is my first thought

loud scroll Sep 28, 2023, 2:16 AM

#

worldly quest why would you say **O(log(n))** and not **O(n^2)**? First thing that come to my ...

I mixed up my other question - sorry. Yes, two loops typically means O(n^2), but what was tripping me up is that i += j in the while loop. that is changing the condition of the loop, so it wouldn’t actually run n times, no?

midnight finch Sep 28, 2023, 2:46 AM

#

;compile perl

my $i = 1;
my $j = 1;
my $run = 0;
$n = 16;
while($i <= $n) { $i = $i + 1; }
print "[$i]\n";

for($j = 1; $j <= $n; ++$j)
{
  $i = $j;
  my $loop = 0;
  while($i <= $n) 
  {
    $i = $i + $j;
    ++$loop;
    ++$run;
  }
  #print "Loop[$i][$n]";
  #print "[$loop] ";
  #print ".";
}

print "\nI[$i] J[$j] N[$n] R[$run]\n ";
exit;

past wedgeBOT Sep 28, 2023, 2:47 AM

#

Program Output

[17]

I[32] J[17] N[16] R[50]

midnight finch Sep 28, 2023, 2:48 AM

#

the inner loop is always n=16

#

the program is timing out

loud scroll Sep 28, 2023, 2:52 AM

#

hm...interesting. i don't fully understand perl syntax, but i guess so. so it'd be O(n^2)

midnight finch Sep 28, 2023, 2:53 AM

#

50 runs for 16

#

16*4 = 64

loud scroll Sep 28, 2023, 2:54 AM

#

so it wouldn't be on^2

midnight finch Sep 28, 2023, 2:54 AM

#

16 log10( 16 ) = 19.26

#

16 log2( 16 ) = 64

#

O(n log2 n)

#

16 ln 16 = 44.36

#

;compile perl

my $i = 1;
my $j = 1;
my $run = 0;
$n = 64;
while($i <= $n) { $i = $i + 1; }
print "[$i]\n";

for($j = 1; $j <= $n; ++$j)
{
  $i = $j;
  my $loop = 0;
  while($i <= $n) 
  {
    $i = $i + $j;
    ++$loop;
    ++$run;
  }
  #print "Loop[$i][$n]";
  #print "[$loop] ";
  #print ".";
}

print "\nI[$i] J[$j] N[$n] R[$run]\n ";
exit;

past wedgeBOT Sep 28, 2023, 2:55 AM

#

Program Output

[65]

I[128] J[65] N[64] R[280]

midnight finch Sep 28, 2023, 2:56 AM

#

2^6 = 64

64*6 = 384

#

so it's better than O(n log2 n)

#

n log3 n = 242

#

n log 2.5 n = 290

#

O(n log 2.58 (n) ) = 281~

#

log2.58(64) = 4.3879822754288

#

16 * 4.3879822754288 = 70.2

#

so a little bit better than O( n LOG2 n )

#

;compile perl

use strict;
use warnings;

my $n = 128;
my $i = 1;
my $j = 1;
my $run = 0;
while($i <= $n) { $i = $i + 1; }
print "[$i]\n";

for($j = 1; $j <= $n; ++$j)
{
  $i = $j;
  my $loop = 0;
  while($i <= $n) 
  {
    $i = $i + $j;
    ++$loop;
    ++$run;
  }
  #print "Loop[$i][$n]";
  #print "[$loop] ";
  #print ".";
}

print "\nI[$i] J[$j] N[$n] R[$run]\n ";
exit;

past wedgeBOT Sep 28, 2023, 3:05 AM

#

Program Output

[129]

I[256] J[129] N[128] R[645]

midnight finch Sep 28, 2023, 3:05 AM

#

128 * 5.04 = 645

#

https://www.calculator.net/log-calculator.html?xv=16&base=2.55&yv=&x=53&y=16

Log Calculator

This free log calculator solves for the unknown portions of a logarithmic expression using base e, 2, 10, or any other desired base.

#

;compile perl

use strict;
use warnings;

my $n = 128;
my $i = 1;
my $j = 1;
my $run = 0;
my $total = 0;
while($i <= $n) { $i = $i + 1; ++$total; }
print "[$i]\n";

for($j = 1; $j <= $n; ++$j)
{
  $i = $j;
  my $loop = 0;
  while($i <= $n) 
  {
    $i = $i + $j;
    ++$loop;
    ++$run;
    ++$total;
  }
  #print "Loop[$i][$n]";
  #print "[$loop] ";
  #print ".";
}

print "\nI[$i] J[$j] N[$n] R[$run] T[$total]\n ";
exit;

past wedgeBOT Sep 28, 2023, 3:16 AM

#

Program Output

[129]

I[256] J[129] N[128] R[645] T[773]

midnight finch Sep 28, 2023, 3:16 AM

#

129 = 128/645/773

#

;compile perl

use strict;
use warnings;

my $n = 4;
my $i = 1;
my $j = 1;
my $run = 0;
my $total = 0;
while($i <= $n) { $i = $i + 1; ++$total; }
print "[$i]\n";

for($j = 1; $j <= $n; ++$j)
{
  $i = $j;
  my $loop = 0;
  while($i <= $n) 
  {
    $i = $i + $j;
    ++$loop;
    ++$run;
    ++$total;
  }
  #print "Loop[$i][$n]";
  #print "[$loop] ";
  #print ".";
}

print "\nI[$i] J[$j] N[$n] R[$run] T[$total]\n ";
exit;

past wedgeBOT Sep 28, 2023, 3:17 AM

#

Program Output

[5]

I[8] J[5] N[4] R[8] T[12]

midnight finch Sep 28, 2023, 3:17 AM

#

4 = 4/8/12
129 = 128/645/773

#

;compile perl

use strict;
use warnings;

sub f($)
{
my $n = $_[0];
my $i = 1;
my $j = 1;
my $run = 0;
my $total = 0;
while($i <= $n) { $i = $i + 1; ++$total; }
#print "[$i]\n";

for($j = 1; $j <= $n; ++$j)
{
  $i = $j;
  my $loop = 0;
  while($i <= $n) 
  {
    $i = $i + $j;
    ++$loop;
    ++$run;
    ++$total;
  }
  #print "Loop[$i][$n]";
  #print "[$loop] ";
  #print ".";
}

my $log = log($n) / log(2);
print "\nI=$i J=$j N=$n R=$run T=$total L=$log";
}

f(1);
f(2);
f(4);
f(8);
f(16);
f(32);
f(64);
f(128);
f(1024);
exit;

past wedgeBOT Sep 28, 2023, 3:18 AM

#

Program Output


I=2 J=2 N=1 R=1 T=2 L=0
I=4 J=3 N=2 R=3 T=5 L=1
I=8 J=5 N=4 R=8 T=12 L=2
I=16 J=9 N=8 R=20 T=28 L=3
I=32 J=17 N=16 R=50 T=66 L=4
I=64 J=33 N=32 R=119 T=151 L=5
I=128 J=65 N=64 R=280 T=344 L=6
I=256 J=129 N=128 R=645 T=773 L=7
I=2048 J=1025 N=1024 R=

fluid gale Sep 28, 2023, 3:22 AM

#

loud scroll I am unsure of how to go about solving this. Obviously lines 1-5 are just O(n), ...

i would classify it as O(n) to be honest, given that the inner loop runs not n times

#

faced a similar leetcode problem which is why i'm saying this

#

but lemme do a little research 1 sec

midnight finch Sep 28, 2023, 3:23 AM

#

it runs in O(n) for n < 5
then faster than O(n log2.5 n)

#

;compile perl

use strict;
use warnings;

sub f($)
{
my $n = $_[0];
my $i = 1;
my $j = 1;
my $run = 0;
my $total = 0;
while($i <= $n) { $i = $i + 1; ++$total; }
#print "[$i]\n";

for($j = 1; $j <= $n; ++$j)
{
  $i = $j;
  my $loop = 0;
  while($i <= $n) 
  {
    $i = $i + $j;
    ++$loop;
    ++$run;
    ++$total;
  }
  #print "Loop[$i][$n]";
  #print "[$loop] ";
  #print ".";
}

my $log = log($n) / log(2.55);
print "\nI=$i J=$j N=$n R=$run T=$total L=$log";
}

f(1);
f(2);
f(4);
f(8);
f(16);
f(32);
f(64);
f(128);
f(1024);
exit;

past wedgeBOT Sep 28, 2023, 3:25 AM

#

Program Output


I=2 J=2 N=1 R=1 T=2 L=0
I=4 J=3 N=2 R=3 T=5 L=0.740468003292199
I=8 J=5 N=4 R=8 T=12 L=1.4809360065844
I=16 J=9 N=8 R=20 T=28 L=2.2214040098766
I=32 J=17 N=16 R=50 T=66 L=2.9618720131688
I=64 J=33 N=32 R=119 T=151 L=3.702340016461
I=128 J=65 N=64 R=

fluid gale Sep 28, 2023, 3:32 AM

#

midnight finch it runs in O(n) for n < 5 then faster than O(n log2.5 n)

that's interesting, I think we can say that the best case is O(n)

#

worst case is O(log(b)n)

midnight finch Sep 28, 2023, 3:32 AM

#

O(n log n)

#

it's 64 * 4

fluid gale Sep 28, 2023, 3:32 AM

#

but the base you used was 2.5, no?

midnight finch Sep 28, 2023, 3:33 AM

#

yes, but you have to multiply the log by N

#

n=64 takes 151 total loops and 119 inner loops O( n + n log2 n)

not 64 + 4 loops 😂 O( n + log2 n)

#

;compile perl

use strict;
use warnings;

sub f($)
{
my $n = $_[0];
my $i = 1;
my $j = 1;
my $run = 0;
my $total = 0;
while($i <= $n) { $i = $i + 1; ++$total; }
#print "[$i]\n";

for($j = 1; $j <= $n; ++$j)
{
  $i = $j;
  my $loop = 0;
  while($i <= $n) 
  {
    $i = $i + $j;
    ++$loop;
    ++$run;
    ++$total;
  }
  #print "Loop[$i][$n]";
  #print "[$loop] ";
  #print ".";
}

my $log = log($n) / log(2.55);
print "\nI=$i J=$j N=$n R=$run T=$total L=$log";
}

#f(1024);
f(1024*1024*16);
#f(1024*1024*1024);
exit;

past wedgeBOT Sep 28, 2023, 3:37 AM

#

Program Output


I=33554432 J=16777217 N=16777216 R=281689074 T=298466290 L=17.7712320790128

#Big O Notation Help