[ModernMoney]

Hey guys,
My difficult to understand prof and poor course notes have been making working through my assignments really tough. If anyone could help me with this problem or lead me in the right direction I would be forever thankful!

Analyze the following pseudo code and give a tight bound on the running time as a function of n. You can assume that all individual instructions are elementary.Show your work.

PHP Code


<?php 
m := 1; s := 1;
while m <= n do
    for j = 1 to 3[logm] do
        s := s + 1
    od
    m := 4*m
od. 


Thank you!!

[SIM-574702]

I'm not going to give you solution but you need to figure out mathematical function that describes that code snippet. Once you have e.g. f(n) = (n/4)*(n^2)... or whatever it ends up you can start doing something I call pseudo math (it's asymptotic behavior but pseudo math is easier to remember).

I'm not sure how much you know about big O, omega and theta notations but you can look them up on internet. I believe the point of this task is to calculate O(n) and Omega(n) and if they are equal you have Theta(n).